2024/02/20 by Steven van den Broek, Broek, Steven van den, Wouter Meulemans +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2402.13340
openalex publication_date 2024/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.