The extensible No-Three-In-Line problem

Abstract

The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an $n\times n$ grid while avoiding a collinear triple. The maximum is well known to be linear in $n$. Following a question of Erde, we seek to select sets of large density from the infinite grid $Z^2$ while avoiding a collinear triple. We show the existence of such a set which contains $\Theta (n/{\log }^{1+\epsilon }n)$ points in $[1,n{]}^2$ for all $n$, where $\epsilon >0$ is an arbitrarily small real number. We also give computational evidence suggesting that a set of lattice points may exist that has at least $n/2$ points on every large enough $n\times n$ grid.

12 pages, 3 figures

References in corpus (1)

• Geometric Dominating Sets