Computing shortest words via shortest loops on hyperbolic surfaces

Xiaotian Yin Yinghua Li Wei Han Feng Luo Xianfeng David Gu Shing-Tung Yau

Geometric Analysis and Geometric Topology mathscidoc:1912.43681

Computer-Aided Design, 43, (11), 1449-1456, 2011.11
Given a loop on a surface, its homotopy class can be specified as a word consisting of letters representing the homotopy group generators. One of the interesting problems is how to compute the shortest word for a given loop. This is an NP-hard problem in general. However, for a closed surface that allows a hyperbolic metric and is equipped with a canonical set of fundamental group generators, the shortest word problem can be reduced to finding the shortest loop that is homotopic to the given loop, which can be solved efficiently. In this paper, we propose an efficient algorithm to compute the shortest words for loops given on triangulated surface meshes. The design of this algorithm is inspired and guided by the work of Dehn and BirmanSeries. In support of the shortest word algorithm, we also propose efficient algorithms to compute shortest paths and shortest loops under hyperbolic metrics using a novel
No keywords uploaded!
[ Download ] [ 2019-12-24 20:49:45 uploaded by yaust ] [ 364 downloads ] [ 0 comments ]
@inproceedings{xiaotian2011computing,
  title={Computing shortest words via shortest loops on hyperbolic surfaces},
  author={Xiaotian Yin, Yinghua Li, Wei Han, Feng Luo, Xianfeng David Gu, and Shing-Tung Yau},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191224204945694106245},
  booktitle={Computer-Aided Design},
  volume={43},
  number={11},
  pages={1449-1456},
  year={2011},
}
Xiaotian Yin, Yinghua Li, Wei Han, Feng Luo, Xianfeng David Gu, and Shing-Tung Yau. Computing shortest words via shortest loops on hyperbolic surfaces. 2011. Vol. 43. In Computer-Aided Design. pp.1449-1456. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20191224204945694106245.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved