Equitable subdivisions within polygonal regions (Q2489545)

The authors prove a generalization of the Ham-Sandwich Theorem, [see \textit{J. E. Goodman} and \textit{J. O'Rourke} (eds.), Handbook of discrete and computational geometry (1997; Zbl 0890.52001)]. Specifically, let \(P\) be a simple polygonal region containing \(| R| =kn\) red points and \(| B| =km\) blue points in its interior with \(k\geq 2\). They 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\). The authors outline an \(O(kN^{2}\log{2}^N)\) time algorithm for computing such a \(k\)-partition, where \(N=| R| +| B| +| P| \).