文章基本信息

标题：Voronoi Diagrams for Parallel Halflines and Line Segments in Space
本地全文：下载
作者：Franz Aurenhammer ; Bert J{\"u}ttler ; G{\"u}nter Paulini 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：92
页码：7:1-7:10
DOI：10.4230/LIPIcs.ISAAC.2017.7
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Voronoi diagram; line segments; space-sweep algorithm