2026-09-05T11:58:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25825 2026-06-23T12:59:04Z ddc:004 open_access

Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements Borzechowski, Michaela Haslebacher, Sebastian Hoang, Hung P. Schnider, Patrick Weber, Simon α-Ham-Sandwich Theorem Pseudo-Hyperplanes Arrangements Unique Sink Orientations Oriented Matroids The famous Ham-Sandwich theorem states that any d point sets in ℝ^d can be simultaneously bisected by a single hyperplane. The α-Ham-Sandwich theorem gives a sufficient condition for the existence of biased cuts, i.e., hyperplanes that do not cut off half but some prescribed fraction of each point set. We give two new proofs for this theorem. The first proof is completely combinatorial and highlights a strong connection between the α-Ham-Sandwich theorem and Unique Sink Orientations of grids. The second proof uses point-hyperplane duality and the Poincaré-Miranda theorem and allows us to generalize the result to and beyond oriented matroids. For this we introduce a new concept of rainbow arrangements, generalizing colored pseudo-hyperplane arrangements. Along the way, we also show that the realizability problem for rainbow arrangements is ∃ℝ-complete, which also implies that the realizability problem for grid Unique Sink Orientations is ∃ℝ-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michaela Borzechowski and Sebastian Haslebacher and Hung P. Hoang and Patrick Schnider and Simon Weber 2026 Is Part Of LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2026.19 urn:nbn:de:0030-drops-258250 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.19 eng https://creativecommons.org/licenses/by/4.0/legalcode