Title: Voronoi Diagrams for Parallel Halflines and Line Segments in Space
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.
Publication Year: 2017
Publication Date: 2017-01-01
Language: en
Type: article
Access and Citation
Cited By Count: 5
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot