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

The author studies the construction of Voronoi diagram of line segments, i.e., for a given set \(S\) of \(n\) line segments in the plane \(\mathbb R^2\) we search for a subdivision of the plane into Voronoi regions defined as \(R(s, S) = \bigcap_{s' \in S \backslash \{s\}} \{x \in \mathbb R^2 : d(x, s)< d(x, s')\}\) , where \(d(x, s)\) denotes the Euclidean distance from point \(x\) to segment \(s\). The study starts with the case of weakly simple polygons, i.e., polygons that have at most two vertices or they can be made simple by an arbitrary small perturbation of their vertices. The proposed method of finding the Voronoi diagram for such polygons is based on the method for simple polygon proposed by \textit{F. Chin} et al. [Discrete Comput. Geom. 21, No. 3, 405--420 (1999; Zbl 0922.68128)]. Then, the authors show that for any weakly simple polygon one can build in linear time a data structure that supports a point location query on the Voronoi diagram of this polygon in logarithmic time. After the case of weakly simple polygons, the author investigates the polygon with holes case. The proposed algorithm has following the strategy. Divide the set of vertices and edges into two sets: (1) forming the outer boundary of the polygon, (2) forming the holes. Then, find independently the Voronoi diagram of the two sets, and finally merge them into one Voronoi diagram. The proposed algorithm computes the Voronoi diagram in \(O(m \log(m+t) + t)\) time, where \(m\) is the total complexity of the holes and \(t\) is the complexity of the outer boundary. Finally, the author considers the computation of the Voronoi diagram of a set \(S\) of \(n\) line segments in the plane \(\mathbb R^2\). The proposed algorithm is divided into three main steps: (1) compute intersection points in \(S\), (2) compute the arrangement of \(S\) (decomposition of \(\mathbb R^2\) into vertices, edges and faces induced by the line segments in \(S\)) and the description of its faces, (3) for every face of the arrangement compute the Voronoi diagram. Then, the resulting Voronoi diagram of the original \(n\) line segments is obtained by taking the union of the face diagrams over all faces of the arrangement. The overall time of the algorithm is \(O(n \alpha(n) \log n + k)\), where \(\alpha\) denotes the functional inverse of the Ackermann function and \(k\) is the number of pairwise intersections of the line segments.