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

摘要

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 alpha(n) logn + k) time, where alpha(.) denotes the inverse of the Ackermann function. The best known running time prior to this work was O ((n + k) logn). Since the lower bound of the problem is shown to be Omega (n logn + k) in the worst case, our algorithm is worst-case optimal for k= Omega (n alpha(n) logn), and is only a factor of 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. (C) 2015 Elsevier B.V. All rights reserved.