Computing Shortest Cycles Using Universal Covering Space
The Visual Computer
Xiaotian Yin, Miao Jin, Xianfeng Gu
In this paper we generalize the shortest path algorithm to
the shortest cycles in each homotopy class on a surface with
arbitrary topology, by utilizing the universal covering space
(UCS) in algebraic topology. In order to store and handle
the UCS, we propose a two-level data structure which is efficient
for storage and easy to process. For the shortest cycle
algorithm and the UCS data structure, we showed some
practical applications, such as topological denoise in geometric
modeling, polygonal schema construction in computational
topology and etc.