Space complexity of exact discrete geodesic algorithms on regular triangulations

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).