No-three-in-line problem

The no-three-in-line problem in discrete geometry asks how many points can be placed in the ${\displaystyle n\times n}$ grid so that no three points lie on the same line. The problem concerns lines of all slopes, not only those aligned with the grid. It was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".^[1]

At most ${\displaystyle 2n}$ points can be placed, because ${\displaystyle 2n+1}$ points in a grid would include a row of three or more points, by the pigeonhole principle. Although the problem can be solved with ${\displaystyle 2n}$ points for every ${\displaystyle n}$ up to ${\displaystyle 46}$, it is conjectured that fewer than ${\displaystyle 2n}$ points can be placed in grids of large size. Known methods can place linearly many points in grids of arbitrary size, but the best of these methods place slightly fewer than ${\displaystyle 1.5n}$ points, not ${\displaystyle 2n}$.

Several related problems of finding points with no three in line, among other sets of points than grids, have also been studied. Although originating in recreational mathematics, the no-three-in-line problem has applications in graph drawing and to the Heilbronn triangle problem.