Greedy Monochromatic Island Partitions

Abstract

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\ge 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 $\mathcal{C}\mathcal{H}(I)\cap S=I$, where $\mathcal{C}\mathcal{H}(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.

13 pages, 12 figures