Convex Equipartitions of Colored Point Sets

Abstract

We show that any d-colored set of points in general position in Rd 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 (Comput Geom 65:35–42, 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 Rd by n convex regions. This gives a convex partition of Rd 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.