Convex equipartitions of colored point sets

Abstract

We show that any $d$-colored set of points in general position in ${\mathbb{R}}^d$ can be partitioned into $n$ subsets with disjoint convex hulls such that the set of points and all color classes are partitioned as evenly as possible. This extends results by Holmsen, Kynčl & Valculescu (2017) and establishes a special case of their general conjecture. Our proof utilizes a result obtained independently by Soberón and by Karasev in 2010, on simultaneous equipartitions of $d$ continuous measures in ${\mathbb{R}}^d$ by $n$ convex regions. This gives a convex partition of ${\mathbb{R}}^d$ with the desired properties, except that points may lie on the boundaries of the regions. In order to resolve the ambiguous assignment of these points, we set up a network flow problem. The equipartition of the continuous measures gives a fractional flow. The existence of an integer flow then yields the desired partition of the point set.

8 pages, 1 figure

References in corpus (1)

• Near equipartitions of colored point sets

Cited by in corpus (2)

• Cutting a part from many measures
• Rainbow polygons for colored point sets in the plane