Measuring similarity between curves on 2-manifolds via homotopy area
Measuring similarity between curves on 2-manifolds via homotopy area
复制标题
通过同伦面积测量 2 流形上曲线之间的相似性
DOI：
--
复制
发表时间：
2013
期刊：
影响因子：
--
通讯作者：
Yusu Wang
中科院分区：
文献类型：
--
作者：
E. Chambers;Yusu Wang
测量曲线的相似度是许多应用领域中遇到的一个基本问题。在欧几里得空间和更一般的情况下，如黎曼曲面上的曲线或平面上减去一组障碍的曲线，人们对几种这样的测量方法都有相当大的兴趣。然而，到目前为止，对于一般曲面上曲线的有效的可计算的相似性度量仍然是难以捉摸的。针对一般可定向2流形上的曲线，提出了一种易于扩展和计算的自然曲线相似测度。具体来说，我们根据一条曲线连续变形为另一条曲线的难度来衡量同伦曲线之间的相似性，并将这种“硬度”定义为曲线之间的同伦所覆盖的最小可能表面积。我们考虑曲线嵌入平面或具有格$g$的三角形可定向曲面的情况，并针对这两种情况提出了有效的算法（根据设置，这些算法要么是二次的，要么是近线性的）。
Measuring the similarity of curves is a fundamental problem arising in many application fields. There has been considerable interest in several such measures, both in Euclidean space and in more general setting such as curves on Riemannian surfaces or curves in the plane minus a set of obstacles. However, so far, efficiently computable similarity measures for curves on general surfaces remain elusive. This paper aims at developing a natural curve similarity measure that can be easily extended and computed for curves on general orientable 2-manifolds. Specifically, we measure similarity between homotopic curves based on how hard it is to deform one curve into the other one continuously, and define this "hardness" as the minimum possible surface area swept by a homotopy between the curves. We consider cases where curves are embedded in the plane or on a triangulated orientable surface with genus $g$, and we present efficient algorithms (which are either quadratic or near linear time, depending on the setting) for both cases.