Constant-time <i>O</i> (1) all pairs geodesic distance query on triangle meshes

Abstract

Geodesic plays an important role in geometric computation and analysis. Rather than the widely studied single source all destination discrete geodesic problem, very little work has been reported on the all pairs geodesic distance query So far, the best known result is due to Cook IV and Wenk [2009], who pre-computed the pairwise geodesic between any two mesh vertices in O(n52α(n) logn) time complexity and O(n4) space complexity, where n is the number of mesh vertices and α(n) the inverse Ackermann function. Then the geodesic distance between any pair of points on the mesh edges can be computed in O(m + logn) time, where m is the number of edges crossed by the geodesic path. Although Cook IV and Wenk's algorithm is able to compute the exact geodesic the high computational cost limits its applications to real-world models which usually contain thousands of vertices.