# zbMATH — the first resource for mathematics

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.

##### MSC:
 68R10 Graph theory (including graph drawing) in computer science 52A10 Convex sets in $$2$$ dimensions (including convex curves) 68W05 Nonnumerical algorithms
##### Keywords:
ham sandwich theorem
Full Text: