An Almost Optimal Algorithm for Voronoi Diagrams of Non-disjoint Line Segments (Extended Abstract)

摘要

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) time, where α(·) denotes the functional inverse of the Ackermann function. The best known running time prior to this work was O((n + k)log n). Since the lower bound of the problem is shown to be Ω(n log n + k) in the worst case, our algorithm is worst-case optimal for k = Ω(nα(n) log n), and is only a factor of α(n) away from the lower bound. For the purpose, we also present an improved algorithm that computes the medial axis or the Voronoi diagram of a polygon with holes.