Voronoi diagrams for parallel halflines and line segments in space

F. Aurenhammer, B. Jüttler, G. Paulini

Research output: Chapter in Book/Report/Conference proceedingConference paperpeer-review

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 languageEnglish
Title of host publicationProc. 28th International Symposium on Algorithms and Computation (ISAAC'17)
Place of PublicationPhuket, Thailand
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages#7
Volume92
ISBN (Electronic)978-395977054-5
DOIs
Publication statusPublished - 2017
Event28th International Symposium on Algorithms and Computation: ISAAC 2017 - Phuket, Thailand
Duration: 9 Dec 201712 Dec 2017

Conference

Conference28th International Symposium on Algorithms and Computation
Country/TerritoryThailand
CityPhuket
Period9/12/1712/12/17

Fingerprint

Dive into the research topics of 'Voronoi diagrams for parallel halflines and line segments in space'. Together they form a unique fingerprint.

Cite this