DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2016.29

Constrained Geodesic Centers of a Simple Polygon

Authors: Eunjin Oh, Wanbin Son, and Hee-Kap Ahn

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

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.

Cite as

Eunjin Oh, Wanbin Son, and Hee-Kap Ahn. Constrained Geodesic Centers of a Simple Polygon. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{oh_et_al:LIPIcs.SWAT.2016.29,
  author =	{Oh, Eunjin and Son, Wanbin and Ahn, Hee-Kap},
  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 =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.29},
  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}
}

Search Results

Documents authored by Son, Wanbin

Constrained Geodesic Centers of a Simple Polygon

Abstract

Cite as

Thanks for your feedback!

Could not send message