2015/01/03 by Hee-Kap Ahn, Luis Barba, Ahn, Hee-Kap +9
Computer Science · Engineering · #Computational Geometry and Mesh Generation #3D Shape Modeling and Analysis #Data Management and Algorithms
paper · pdf · doi:10.48550/arxiv.1501.00561
Given two points in a simple polygon P of n vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. & Comput. Geom. 89] showed an O(nlog n)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.