Abstract
We consider the Euclidean Voronoi diagram for a set of n parallel halflines in R3. 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.
Original language | English |
---|---|
Title of host publication | Proc. 28th International Symposium on Algorithms and Computation (ISAAC'17) |
Place of Publication | Phuket, Thailand |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Pages | #7 |
Volume | 92 |
ISBN (Electronic) | 978-395977054-5 |
DOIs | |
Publication status | Published - 2017 |
Event | 28th International Symposium on Algorithms and Computation: ISAAC 2017 - Phuket, Thailand Duration: 9 Dec 2017 → 12 Dec 2017 |
Conference
Conference | 28th International Symposium on Algorithms and Computation |
---|---|
Country/Territory | Thailand |
City | Phuket |
Period | 9/12/17 → 12/12/17 |