Tight Bound for Farthest-Color Voronoi Diagrams of Line Segments

摘要

We establish a tight bound on the worst-case combinatorial complexity of the farthest-color Voronoi diagram of line segments in the plane. More precisely, given k sets of total n line segments, the combinatorial complexity of the farthest-color Voronoi diagram is shown to be Θ(kn + h) in the worst case, under any L_p metric with 1 ≤ p ≤ ∞, where h is the number of crossings between the n line segments. We also show that the diagram can be computed in optimal O((kn + h)log n) time under the L_1 or L∞ metric, or in O((kn + h)(α(k)log k + log n)) time under the L_p metric for any 1 < p < ∞, where α(·) denotes the inverse Ackermann function.