Greedy Monochromatic Island Partitions

Constructing partitions of colored points is a well-studied problem in discrete and computational geometry. We study the problem of creating a minimum-cardinality partition into monochromatic islands. Our input is a set S of n points in the plane where each point has one of k ≥ 2 colors. A set of points is monochromatic if it contains points of only one color. An island I is a subset of S such that CH(I) ∩ S = I, where CH(I) denotes the convex hull of I. We identify an island with its convex hull; therefore, a partition into islands has the additional requirement that the convex hulls of the islands are pairwise-disjoint. We present three greedy algorithms for constructing island partitions and analyze their approximation ratios.