A Purely Geometric Variant of the Gale-Berlekamp Switching Game

Abstract

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\to \infty$, and at least $n/3$, for every $n$. Moreover, these can be attained by a polynomial time algorithm.

11 pages, 3 figures