Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Kim, Mincheol; Seo, Chanyang; Ahn, Taehoon; Ahn, Hee-Kap https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-160596
URL:

; ; ;

Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles

pdf-format:


Abstract

We present an algorithm to compute the geodesic L₁ farthest-point Voronoi diagram of m point sites in the presence of n rectangular obstacles in the plane. It takes O(nm+n log n + mlog m) construction time using O(nm) space. This is the first optimal algorithm for constructing the farthest-point Voronoi diagram in the presence of obstacles. We can construct a data structure in the same construction time and space that answers a farthest-neighbor query in O(log(n+m)) time.

BibTeX - Entry

@InProceedings{kim_et_al:LIPIcs.SoCG.2022.51,
  author =	{Kim, Mincheol and Seo, Chanyang and Ahn, Taehoon and Ahn, Hee-Kap},
  title =	{{Farthest-Point Voronoi Diagrams in the Presence of Rectangular Obstacles}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{51:1--51:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16059},
  URN =		{urn:nbn:de:0030-drops-160596},
  doi =		{10.4230/LIPIcs.SoCG.2022.51},
  annote =	{Keywords: Geodesic distance, L₁ metric, farthest-point Voronoi diagram}
}

Keywords: Geodesic distance, L₁ metric, farthest-point Voronoi diagram
Seminar: 38th International Symposium on Computational Geometry (SoCG 2022)
Issue date: 2022
Date of publication: 01.06.2022


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