文章基本信息

标题：A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon
本地全文：下载
作者：Hee Kap Ahn ; Luis Barba ; Prosenjit Bose 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2015
卷号：34
页码：209-223
DOI：10.4230/LIPIcs.SOCG.2015.209
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Let P be a closed simple polygon with n vertices. For any two points in P, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in 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(n log 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.
关键词：Geodesic distance; facility location; 1-center problem; simple polygons