TY - GEN

T1 - Canonical homotopy class representative using hyperbolic structure

AU - Zeng, Wei

AU - Jin, Miao

AU - Luo, Feng

AU - Gu, Xianfeng David

PY - 2009/11/20

Y1 - 2009/11/20

N2 - Homotopy group plays a role in computational topology with a fundamental importance. Each homotopy equivalence class contains an infinite 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 flow 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 efficiency and efficacy of the algorithm. The unique homotopy class representative can be applied for homotopy detection and shape comparison.

AB - Homotopy group plays a role in computational topology with a fundamental importance. Each homotopy equivalence class contains an infinite 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 flow 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 efficiency and efficacy of the algorithm. The unique homotopy class representative can be applied for homotopy detection and shape comparison.

KW - Homotopy class

KW - Hyperbolic Yamabe flow

KW - Hyperbolic structure

UR - http://www.scopus.com/inward/record.url?scp=70349888083&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70349888083&partnerID=8YFLogxK

U2 - 10.1109/SMI.2009.5170145

DO - 10.1109/SMI.2009.5170145

M3 - Conference contribution

AN - SCOPUS:70349888083

SN - 9781424440702

T3 - 2009 IEEE International Conference on Shape Modeling and Applications, SMI 2009

SP - 171

EP - 178

BT - 2009 IEEE International Conference on Shape Modeling and Applications, SMI 2009

T2 - 2009 IEEE International Conference on Shape Modeling and Applications, SMI 2009

Y2 - 26 June 2009 through 28 June 2009

ER -