## Pavle V. M. Blagojević, Günter Rote, Johanna K. Steinmeyer, and
Günter M. Ziegler:

# Convex equipartitions of colored point sets

Manuscript, May 2017, 7 pages, arXiv:1705.03953 [math.CO].
### Abstract

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: May 12, 2017.