Paul Goldsman and I have devised a procedure that solves some partitioning problems, such as cutting a cake fairly or constructing ham-sandwich cuts.
In two dimensions the ham-sandwich problem in computational geometry asks for a single straight line that simultaneously divides two sets of points. Here is how we construct that median line: Imagine that salt and pepper distributed over the top of a lazy susan. Two people sit opposite each other. One holds his knife over the median point for salt and one over the median point for pepper. As the lazy susan is rotated, each person adjusts the position of his knife as necessary to divide “his” set of points, but always keeping the knife vertical. Because the location of the median x value varies continuously with the angle of rotation, by the Intermediate Value Theorem of calculus, there exists an angle at which the knives will coincide. This will be found before the lazy susan has rotated through an angle of pi radians, as illustrated below, where a yellow flash indicates when the knives coincide and a ham-sandwich cut (that is, a common median line) has been found.
This approach can be implemented as a binary search over the angle of rotation, which is continued until the two median lines are “sufficiently close”, after which a single line can be identified that is the ham-sandwich cut. The resulting algorithm runs in O(n) time when there are n points. Details may be found in an academic paper currently under review.
The same idea can be used to construct fast approximate ham-sandwich cuts of other structures, such as simple polygons.