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.ESA.2016.77
URN: urn:nbn:de:0030-drops-64189
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6418/
Go to the corresponding LIPIcs Volume Portal

Wang, Haitao

On the Geodesic Centers of Polygonal Domains

pdf-format:
LIPIcs-ESA-2016-77.pdf (0.6 MB)

Abstract

In this paper, we study the problem of computing Euclidean geodesic centers of a polygonal domain P of n vertices. We give a necessary condition for a point being a geodesic center. We show that there is at most one geodesic center among all points of P that have topologically-equivalent shortest path maps. This implies that the total number of geodesic centers is bounded by the size of the shortest path map equivalence decomposition of P, which is known to be O(n^{10}). One key observation is a pi-range property on shortest path lengths when points are moving. With these observations, we propose an algorithm that computes all geodesic centers in O(n^{11}*log(n)) time. Previously, an algorithm of O(n^{12+epsilon}) time was known for this problem, for any epsilon > 0.

BibTeX - Entry

@InProceedings{wang:LIPIcs:2016:6418,
  author =	{Haitao Wang},
  title =	{{On the Geodesic Centers of Polygonal Domains}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{77:1--77:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Piotr Sankowski and Christos Zaroliagis},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6418},
  URN =		{urn:nbn:de:0030-drops-64189},
  doi =		{10.4230/LIPIcs.ESA.2016.77},
  annote =	{Keywords: geodesic centers, shortest paths, polygonal domains}
}

Keywords: geodesic centers, shortest paths, polygonal domains
Collection: 24th Annual European Symposium on Algorithms (ESA 2016)
Issue Date: 2016
Date of publication: 18.08.2016

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