Geometric Give and Take
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918379877564416 |
|---|---|
| author | Aichholzer, Oswin Klost, Katharina Knorr, Kristin Mészáros, Viola Tkadlec, Josef |
| author_facet | Aichholzer, Oswin Klost, Katharina Knorr, Kristin Mészáros, Viola Tkadlec, Josef |
| contents | We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement $\mathcal{L}$ of $n$ lines in the plane, and assume that each cell of the arrangement contains a box. Alice initially places pebbles in each box. In each subsequent step, Bob picks a line, and Alice must choose a side of that line, remove one pebble from each box on that side, and add one pebble to each box on the other side. Bob wins if any box ever becomes empty. We determine the minimum number $f(\mathcal L)$ of pebbles, computable in polynomial time, for which Alice can prevent Bob from ever winning, and we show that $f(\mathcal L)=Θ(n^3)$ for any arrangement $\mathcal{L}$ of $n$ lines in general position. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_08074 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Geometric Give and Take Aichholzer, Oswin Klost, Katharina Knorr, Kristin Mészáros, Viola Tkadlec, Josef Computational Geometry F.2.2; I.3.5 We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement $\mathcal{L}$ of $n$ lines in the plane, and assume that each cell of the arrangement contains a box. Alice initially places pebbles in each box. In each subsequent step, Bob picks a line, and Alice must choose a side of that line, remove one pebble from each box on that side, and add one pebble to each box on the other side. Bob wins if any box ever becomes empty. We determine the minimum number $f(\mathcal L)$ of pebbles, computable in polynomial time, for which Alice can prevent Bob from ever winning, and we show that $f(\mathcal L)=Θ(n^3)$ for any arrangement $\mathcal{L}$ of $n$ lines in general position. |
| title | Geometric Give and Take |
| topic | Computational Geometry F.2.2; I.3.5 |
| url | https://arxiv.org/abs/2603.08074 |