The Farthest Color Voronoi Diagram in the Plane

The farthest-color Voronoi diagram (FCVD) is defined on a set of <i>n</i> points in the plane, where each point is labeled with one of <i>m</i> colors. The colored points constitute a family <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mi>P</mml:mi></mml:math> of <i>m</i> clusters (sets) of points in the plane whose farthest-site Voronoi diagram is the FCVD. The diagram finds applications in problems related to facility location, shape matching, data imprecision, and others. In this paper we present structural properties of the FCVD, refine its combinatorial complexity bounds, and present efficient algorithms for its construction. We show that the complexity of the diagram is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mi>α</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>+</mml:mo> <mml:mi>str</mml:mi> <mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , where <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>str</mml:mi> <mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> is a parameter reflecting the number of <i>straddles</i> between pairs of clusters, which is <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>m</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>-</mml:mo> <mml:mi>m</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo></mml:mrow> </mml:math> . The bound reduces to <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>str</mml:mi> <mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>)</mml:mo> <mml:mo>)</mml:mo></mml:mrow> </mml:math> if the clusters are pairwise <i>non-crossing</i>. We also present a lower bound, establishing that the complexity of the FCVD can be <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>Ω</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:msup><mml:mi>m</mml:mi> <mml:mn>2</mml:mn></mml:msup> <mml:mo>)</mml:mo></mml:mrow> </mml:math> , even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>+</mml:mo> <mml:mi>str</mml:mi> <mml:mrow><mml:mo>(</mml:mo> <mml:mi>P</mml:mi> <mml:mo>)</mml:mo></mml:mrow> <mml:mo>)</mml:mo></mml:mrow> <mml:msup><mml:mo>log</mml:mo> <mml:mn>3</mml:mn></mml:msup> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> -time, and in certain special cases in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:mi>n</mml:mi> <mml:mo>log</mml:mo> <mml:mi>n</mml:mi> <mml:mo>)</mml:mo></mml:mrow> </mml:math> time.