Faster Approximations of Shortest Geodesic Paths on Polyhedra Through Adaptive Priority Queue

Abstract

Computing shortest geodesic paths is a crucial problem in several application areas, including robotics, medical imaging, terrain navigation and computational geometry. This type of computation on triangular meshes helps to solve different tasks, such as mesh watermarking, shape classification and mesh parametrization. In this work, a priority queue based on a bucketing structure is applied to speed up graph-based methods that approximates shortest geodesic paths on polyhedra. Initially, the problem is stated, some of its properties are discussed and a review of relevant methods is presented. Finally, we describe the proposed method and show several results and comparisons that confirm its benefits.