We show that any d-colored set of points in general position in d dimensions 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, and Valculescu (2017) and establishes a central case of their general conjecture. Our proof utilizes a result of Soberón (2012) on simultaneous equipartitions of d continuous measures in d-space by n convex regions, which gives a convex partition 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.
Last update: February 5, 2019.