Equitable subdivisions within polygonal regions

AbstractWe prove a generalization of the Ham-Sandwich Theorem. Specifically, let P be a simple polygonal region containing |R|=kn red points and |B|=km blue points in its interior with k⩾2. We show that P can be partitioned into k relatively-convex regions each of which contains exactly n red and m blue points. A region of P is relatively-convex if it is closed under geodesic (shortest) paths in P. We outline an O(kN2log2N) time algorithm for computing such a k-partition, where N=|R|+|B|+|P|