Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908827692040192 |
|---|---|
| author | Borzechowski, Michaela Haslebacher, Sebastian Hoang, Hung P. Schnider, Patrick Weber, Simon |
| author_facet | Borzechowski, Michaela Haslebacher, Sebastian Hoang, Hung P. Schnider, Patrick Weber, Simon |
| contents | The famous Ham-Sandwich theorem states that any $d$ point sets in $\mathbb{R}^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 $\exists \mathbb{R}$-complete, which also implies that the realizability problem for grid Unique Sink Orientations is $\exists \mathbb{R}$-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_10795 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements Borzechowski, Michaela Haslebacher, Sebastian Hoang, Hung P. Schnider, Patrick Weber, Simon Combinatorics Computational Geometry The famous Ham-Sandwich theorem states that any $d$ point sets in $\mathbb{R}^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 $\exists \mathbb{R}$-complete, which also implies that the realizability problem for grid Unique Sink Orientations is $\exists \mathbb{R}$-complete. |
| title | Splitting Sandwiches Unevenly via Unique Sink Orientations and Rainbow Arrangements |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2602.10795 |