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


Aurenhammer, Franz ; Jüttler, Bert ; Paulini, Günter

Voronoi Diagrams for Parallel Halflines and Line Segments in Space

pdf-format:
LIPIcs-ISAAC-2017-7.pdf (0.6 MB)


Abstract

We consider the Euclidean Voronoi diagram for a set of $n$ parallel halflines in 3-space. A relation of this diagram to planar power diagrams is shown, and is used to analyze its geometric and topological properties. Moreover, an easy-to-implement space sweep algorithm is proposed that computes the Voronoi diagram for parallel halflines at logarithmic cost per face. Previously only an approximation algorithm for this problem was known. Our method of construction generalizes to Voronoi diagrams for parallel line segments, and to higher dimensions.

BibTeX - Entry

@InProceedings{aurenhammer_et_al:LIPIcs:2017:8215,
  author =	{Franz Aurenhammer and Bert J{\"u}ttler and G{\"u}nter Paulini},
  title =	{{Voronoi Diagrams for Parallel Halflines and Line Segments in Space}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{7:1--7:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Yoshio Okamoto and Takeshi Tokuyama},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/8215},
  URN =		{urn:nbn:de:0030-drops-82157},
  doi =		{10.4230/LIPIcs.ISAAC.2017.7},
  annote =	{Keywords: Voronoi diagram, line segments, space-sweep algorithm}
}

Keywords: Voronoi diagram, line segments, space-sweep algorithm
Seminar: 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Issue Date: 2017
Date of publication: 04.12.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI