Farthest Color Voronoi Diagrams: Complexity and Algorithms

The farthest-color Voronoi diagram (FCVD) is a farthest-site Voronoi structure defined on a family \(\mathcal {P} \) of m point-clusters in the plane, where the total number of points is n. The FCVD finds applications in problems related to color spanning objects and facility location. We identify structural properties of the FCVD, refine its combinatorial complexity bounds, and list conditions under which the diagram has O(n) complexity. We show that the diagram may have complexity \(\varOmega (n+m^2)\) even if clusters have disjoint convex hulls. We present construction algorithms with running times ranging from \(O(n\log n)\), when certain conditions are met, to \(O((n+s(\mathcal {P} ))\log ^3n)\) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in \(\mathcal {P} \) (\(s(P)\in O(mn)\)). A pair of points \(q_1,q_2\in Q\) is said to straddle \(p_1,p_2\in P\) if the line segment \(q_1q_2\) intersects (straddles) the line through \(p_1,p_2\) and the disks through \((p_1,p_2,q_1)\) and \((p_1,p_2,q_2)\) contain no points of P, Q. The complexity of the diagram is shown to be \(O(n+s(\mathcal {P} ))\).