PARTITIONING COLORED POINT SETS INTO MONOCHROMATIC PARTS
Adrian Dumitrescu, János Pach · International Journal of Computational Geometry & Applications · 2002
We show that any two-colored set of n points in general position in the plane can be partitioned into at most [Formula: see text] monochromatic subsets, whose convex hulls are pairwise disjoint. This bound cannot be improved in general. We present an O(n log n) time algorithm for constructing a partition into fewer parts, if the coloring is unbalanced, i.e., the sizes of the two color classes differ by more than one. The analogous question for k-colored point sets (k > 2) and its higher dimensional variant are also considered.