An almost optimal algorithm for Voronoi diagrams of non-disjoint line segments

详细信息    查看全文

• 作者：Sang Won Bae ^{swbae@kgu.ac.kr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Voronoi diagram ; Line segments ; Weakly simple polygon ; Polygon with holes ; Medial axis
• 刊名：Computational Geometry
• 出版年：2016
• 出版时间：February 2016
• 年：2016
• 卷：52
• 期：Complete
• 页码：34-43
• 全文大小：385 K

文摘

This paper presents an almost optimal algorithm that computes the Voronoi diagram of a set S of n line segments that may intersect or cross each other. If there are k intersections among the input segments in S  , our algorithm takes O(nα(n)log⁡n+k)$O(n\alpha (n)\log n+k)$ time, where α(⋅)$\alpha (\cdot )$ denotes the inverse of the Ackermann function. The best known running time prior to this work was O((n+k)log⁡n)$O((n+k)\log n)$. Since the lower bound of the problem is shown to be Ω(nlog⁡n+k)$\mathrm{\Omega }(n\log n+k)$ in the worst case, our algorithm is worst-case optimal for k=Ω(nα(n)log⁡n)$k=\mathrm{\Omega }(n\alpha (n)\log n)$, and is only a factor of α(n)$\alpha (n)$ away from any optimal-time algorithm, which is still unknown. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.