Near equipartitions of colored point sets

Abstract

Suppose that $nk$ points in general position in the plane are colored red and blue, with at least $n$ points of each color. We show that then there exist $n$ pairwise disjoint convex sets, each of them containing $k$ of the points, and each of them containing points of both colors. We also show that if $P$ is a set of $n(d+1)$ points in general position in ${\mathbb{R}}^d$ colored by $d$ colors with at least $n$ points of each color, then there exist $n$ pairwise disjoint $d$-dimensional simplices with vertices in $P$, each of them containing a point of every color. These results can be viewed as a step towards a common generalization of several previously known geometric partitioning results regarding colored point sets.

13 pages, 5 figures; new simple proof of Lemma 4

Cited by in corpus (4)

• Convex equipartitions of colored point sets
• Cutting a part from many measures
• An efficient algorithm for identifying rainbow ortho-convex 4-sets in k-colored point sets
• Rainbow polygons for colored point sets in the plane