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

Oh, Eunjin ; Son, Wanbin ; Ahn, Hee-Kap

Constrained Geodesic Centers of a Simple Polygon

pdf-format:
LIPIcs-SWAT-2016-29.pdf (0.5 MB)

Abstract

For any two points in a simple polygon P, the geodesic distance between them is the length of the shortest path contained in P that connects them. A geodesic center of a set S of sites (points) with respect to P is a point in P that minimizes the geodesic distance to its farthest site. In many realistic facility location problems, however, the facilities are constrained to lie in feasible regions. In this paper, we show how to compute the geodesic centers constrained to a set of line segments or simple polygonal regions contained in P. Our results provide substantial improvements over previous algorithms.

BibTeX - Entry

@InProceedings{oh_et_al:LIPIcs:2016:6051,
  author =	{Eunjin Oh and Wanbin Son and Hee-Kap Ahn},
  title =	{{Constrained Geodesic Centers of a Simple Polygon}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Rasmus Pagh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6051},
  URN =		{urn:nbn:de:0030-drops-60516},
  doi =		{10.4230/LIPIcs.SWAT.2016.29},
  annote =	{Keywords: Geodesic distance, simple polygons, constrained center, facility location, farthest-point Voronoi diagram}
}

Keywords: Geodesic distance, simple polygons, constrained center, facility location, farthest-point Voronoi diagram
Collection: 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Issue Date: 2016
Date of publication: 22.06.2016

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