Generalizing ham sandwich cuts to equitable subdivisions. (English) Zbl 0966.68156

Summary: We prove a generalization of the famous ham sandwich theorem for the plane. Given \(gn\) red points and \(gm\) blue points in the plane in general position, there exists an equitable subdivision of the plane into \(g\) disjoint convex polygons, each of which contains \(n\) red points and \(m\) blue points. For \(g= 2\) this problem is equivalent to the ham sandwich theorem in the plane. We also present an efficient algorithm for constructing an equitable subdivision.


68R10 Graph theory (including graph drawing) in computer science
52A10 Convex sets in \(2\) dimensions (including convex curves)
68W05 Nonnumerical algorithms
Full Text: DOI