License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.52
URN: urn:nbn:de:0030-drops-72184
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7218/
Go to the corresponding LIPIcs Volume Portal


Oh, Eunjin ; Ahn, Hee-Kap

Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon

pdf-format:
LIPIcs-SoCG-2017-52.pdf (0.6 MB)


Abstract

Given a set of sites in a simple polygon, a geodesic Voronoi diagram partitions the polygon into regions based on distances to sites under the geodesic metric. We present algorithms for computing the geodesic nearest-point, higher-order and farthest-point Voronoi diagrams of m point sites in a simple n-gon, which improve the best known ones for m < n/polylog n. Moreover, the algorithms for the nearest-point and farthest-point Voronoi diagrams are optimal for m < n/polylog n. This partially answers a question posed by Mitchell in the Handbook of Computational Geometry.

BibTeX - Entry

@InProceedings{oh_et_al:LIPIcs:2017:7218,
  author =	{Eunjin Oh and Hee-Kap Ahn},
  title =	{{Voronoi Diagrams for a Moderate-Sized Point-Set in a Simple Polygon}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7218},
  URN =		{urn:nbn:de:0030-drops-72184},
  doi =		{10.4230/LIPIcs.SoCG.2017.52},
  annote =	{Keywords: Simple polygons, Voronoi diagrams, geodesic distance}
}

Keywords: Simple polygons, Voronoi diagrams, geodesic distance
Seminar: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 08.06.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI