Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950879 | Information Processing Letters | 2017 | 5 Pages |
Abstract
Computing geodesic distances on 2-manifold meshes is a fundamental problem in computational geometry. To date, two notable classes of exact algorithms, namely, the Mitchell-Mount-Papadimitriou (MMP) algorithm and the Chen-Han (CH) algorithm, have been widely studied. For an arbitrary triangle mesh with n vertices, these algorithms have space complexity of O(n2). In this paper, we prove that both algorithms have Î(n1.5) space complexity on a completely regular triangulation (i.e., all triangles are equilateral).
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Yong-Jin Liu, Dian Fan, Chunxu Xu, Ying He,