Canonical Homotopy Class Representative Using Hyperbolic Structure

摘要：

Homotopy group plays a role in computational topology with a fundamental importance. Each homotopy equivalence class contains an innite number of loops. Finding a canonical representative within a homotopy class will simplify many computational tasks in computational topology, such as loop homotopy detection, pants decomposition. Furthermore, the canonical representative can be used as the shape descriptor. This work introduces a rigorous and practical method to compute a unique representative for each homotopy class. The main strategy is to use hyperbolic structure, such that each homotopy class has a unique closed geodesic, which is the representative. The following is the algorithm pipeline: for a given surface with negative Euler number, we apply hyperbolic Yamabe curvature ow to compute the unique Riemannian metric, which has constant negative one curvature everywhere and is conformal to the original metric. Then we compute the Fuchsian group generators of the surface on the hyperbolic space. For a given loop on the surface, we lift it to the universal covering space, to obtain the Fuchsian transformation corresponding to the homotopy class of the loop. The unique closed geodesic inside the homotopy class is the axis of the Fuchsian transformation, which is the canonical representative. Theories and algorithms are explained thoroughly in details. Experimental results are reported to show the efciency and efcacy of the algorithm. The unique homotopy class representative can be applied for homotopy detection and shape comparison.

关键词： homotopy class hyperbolic structure hyperbolic Yamabe flow

作者: Wei Zeng Miao Jin Feng Luo Xianfeng David Gu

作者单位: Department of Computer Science, Stony Brook University, Stony Brook, NY 11794, USA Center for Advanced Computer Studies, University of Louisiana at Lafayette, Lafayette, LA 70504, USA Department of Mathematics, Rutgers University, Piscataway, NJ 08854, USA

会议类型: 国际会议

会议名称: IEEE International Conference on Shape Modeling and Applications (SMI)(2009年形状建模国际会议)

会议地点: 北京

会议语种:英文

页码: 171-178

在线出版日期: 2009-06-26（万方平台首次上网日期，不代表论文的发表时间）