We show that any two-colored set of n points in general position in the plane can be partitioned into at most $\lceil\frac{n+1}{2}\rceil$ 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.
['Adrian Dumitrescu', 'János Pach']
Partitioning colored point sets into monochromatic parts