Farthest color Voronoi diagrams: complexity and algorithms

Abstract

The farthest-color Voronoi diagram (FCVD) is a farthestsite Voronoi structure defined on a family 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 ¿(n + m2 ) 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(P)) log3 n) in general, where s(P) is a parameter reflecting the number of straddles between pairs of clusters in P (s(P) ¿ O(mn)). A pair of points q1, q2 ¿ Q is said to straddle p1, p2 ¿ P if the line segment q1q2 intersects (straddles) the line through p1, p2 and the disks through (p1, p2, q1) and (p1, p2, q2) contain no points of P, Q. The complexity of the diagram is shown to be O(n + s(P)).

Peer Reviewed

Postprint (author's final draft)