Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
414589 | Computational Geometry | 2016 | 10 Pages |
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)logn+k)O(nα(n)logn+k) time, where α(⋅)α(⋅) denotes the inverse of the Ackermann function. The best known running time prior to this work was O((n+k)logn)O((n+k)logn). Since the lower bound of the problem is shown to be Ω(nlogn+k)Ω(nlogn+k) in the worst case, our algorithm is worst-case optimal for k=Ω(nα(n)logn)k=Ω(nα(n)logn), and is only a factor of α(n)α(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.