{"id":"arxiv/2607.02400","url":"https://arxiv.org/abs/2607.02400","tags":["cs.CG","math.CO","math.MG"],"score":0,"title":"From Ham-Sandwich to Centerpoints: Semialgebraic Algorithms for Cutting Polytopal Measures","domain":"cs.CG","source":"arxiv","authors":["Marie-Charlotte Brandenburg","Jesús A. De Loera","Chiara Meroni"],"reviews":0,"subject":"cs.CG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}