License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SOCG.2015.209
URN: urn:nbn:de:0030-drops-51448
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5144/
Go to the corresponding LIPIcs Volume Portal

Ahn, Hee Kap ; Barba, Luis ; Bose, Prosenjit ; De Carufel, Jean-Lou ; Korman, Matias ; Oh, Eunjin

A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon

pdf-format:
61.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{ahn_et_al:LIPIcs:2015:5144,
  author =	{Hee Kap Ahn and Luis Barba and Prosenjit Bose and Jean-Lou De Carufel and Matias Korman and Eunjin Oh},
  title =	{{A Linear-Time Algorithm for the Geodesic Center of a Simple Polygon}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{209--223},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Lars Arge and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5144},
  URN =		{urn:nbn:de:0030-drops-51448},
  doi =		{10.4230/LIPIcs.SOCG.2015.209},
  annote =	{Keywords: Geodesic distance, facility location, 1-center problem, simple polygons}
}

Keywords: Geodesic distance, facility location, 1-center problem, simple polygons
Collection: 31st International Symposium on Computational Geometry (SoCG 2015)
Issue Date: 2015
Date of publication: 12.06.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI