From Ham-Sandwich to Centerpoints: Semialgebraic Algorithms for Cutting Polytopal Measures
For computational geometry researchers, this provides the first exact algorithms for these fundamental cutting problems with polytopal measures, though the fixed-dimension assumption limits practical impact.
The authors design exact polynomial-time algorithms for ham-sandwich cuts and centerpoints for polytopal measures in fixed dimension, showing that the set of centerpoints of a convex polytope coincides with its floating body at level 1/(d+1).
We design exact algorithms for the ham-sandwich and centerpoint theorems for polytopal measures. Our key observation is that the cap-volume function of such a measure, i.e., the volume cut off by a halfspace, is piecewise rational on a natural decomposition of the space of oriented hyperplanes. This lets us recast prescribed-proportion cutting problems as semialgebraic feasibility problems. For fixed ambient dimension, this yields polynomial-time algorithms to decide the existence of cuts, describe the full solution set, and sample or enumerate solutions. We extend this framework to the center transversal theorem, showing that spaces of deep affine flats are semialgebraic, which holds for centerpoints. We further show that the set of centerpoints of a convex polytope coincides with its floating body at level $1/(d+1)$, a useful semialgebraic description.