1 Search Results for "Son, Wanbin"


Document
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-dev.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}
}
  • Refine by Author
  • 1 Ahn, Hee-Kap
  • 1 Oh, Eunjin
  • 1 Son, Wanbin

  • Refine by Classification

  • Refine by Keyword
  • 1 Geodesic distance
  • 1 constrained center
  • 1 facility location
  • 1 farthest-point Voronoi diagram
  • 1 simple polygons

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2016

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail