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

# Convex equipartitions of colored point sets

*Discrete and Computational
Geometry* **61** (2019), 355–363,
doi:10.1007/s00454-017-9959-7,
arXiv:1705.03953 [math.CO].
→BibTeX
### 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: February 5, 2019.