LIPIcs.ISAAC.2017.7.pdf
- Filesize: 0.56 MB
- 10 pages
Document
Voronoi Diagrams for Parallel Halflines and Line Segments in Space
Authors
-
Part of:
Volume:
28th International Symposium on Algorithms and Computation (ISAAC 2017)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Symposium on Algorithms and Computation (ISAAC) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-12-07
Cite AsGet BibTex
Franz Aurenhammer, Bert Jüttler, and Günter Paulini. Voronoi Diagrams for Parallel Halflines and Line Segments in Space. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 7:1-7:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ISAAC.2017.7
https://doi.org/10.4230/LIPIcs.ISAAC.2017.7
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.
Keywords
- Voronoi diagram
- line segments
- space-sweep algorithm
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads