The farthest color Voronoi diagram in the plane

The farthest-color Voronoi diagram (FCVD) is defined on a set of $n$ points in the plane, each of which is labeled with one of $m$ colors.The colored points can be seen as a family $\cC$ of$m$ 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, imprecision in geometric data, sensor deployment, 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 $O(n\alpha(n)+\str(\cC))$, where $\str(\cC)$ is a parameter reflecting the number of straddles between pairs of clusters, which is $O(m(n-m))$. The bound reduces to $O(n+ \str(\cC))$ if the clusters are pairwise non-crossing. We also present a lower bound, establishing that the complexity of the FCVD can be $\Omega(n+m^2)$, even if the clusters have pairwise disjoint convex hulls. Our algorithm runs in $O((n+\str(\cC))\log^3 n)$-time, and in certain special cases in $O(n\log n)$ time.