Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2502.16305 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _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 |