Greedy Monochromatic Island Partitions
<|reference_start|>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 \geq 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{CH}(I) \cap S = I$, where $\mathcal{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.<|reference_end|>
@article{broek2024greedy,
    title={Greedy Monochromatic Island Partitions},
    author={Steven van den Broek, Wouter Meulemans, Bettina Speckmann},
    journal={arXiv preprint arXiv:2402.13340},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.13340},
    primaryClass={cs.CG}
}