A Purely Geometric Variant of the Gale-Berlekamp Switching Game
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916903752040448 |
|---|---|
| author | Dumitrescu, Adrian Lim, Jeck Pach, János Zeng, Ji |
| author_facet | Dumitrescu, Adrian Lim, Jeck Pach, János Zeng, Ji |
| contents | We introduce the following variant of the Gale-Berlekamp switching game. Let $P$ be a set of n noncollinear points in the plane, each of them having weight $+1$ or $-1$. At each step, we pick a line $\ell$ passing through at least two points of $P$, and switch the sign of every point $p \in P\cap\ell$. The objective is to maximize the total weight of the elements of $P$. We show that one can always achieve that this quantity is at least $n - o(n)$, as $n\rightarrow\infty$, and at least $n/3$, for every $n$. Moreover, these can be attained by a polynomial time algorithm. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_16305 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A Purely Geometric Variant of the Gale-Berlekamp Switching Game Dumitrescu, Adrian Lim, Jeck Pach, János Zeng, Ji Computational Geometry Combinatorics We introduce the following variant of the Gale-Berlekamp switching game. Let $P$ be a set of n noncollinear points in the plane, each of them having weight $+1$ or $-1$. At each step, we pick a line $\ell$ passing through at least two points of $P$, and switch the sign of every point $p \in P\cap\ell$. The objective is to maximize the total weight of the elements of $P$. We show that one can always achieve that this quantity is at least $n - o(n)$, as $n\rightarrow\infty$, and at least $n/3$, for every $n$. Moreover, these can be attained by a polynomial time algorithm. |
| title | A Purely Geometric Variant of the Gale-Berlekamp Switching Game |
| topic | Computational Geometry Combinatorics |
| url | https://arxiv.org/abs/2502.16305 |