Combinatorics | Lattice points | Mathematical problems | Conjectures
No-three-in-line problem
The no-three-in-line problem in discrete geometry asks how many points can be placed in the grid so that no three points lie on the same line. This number is at most , because points in a grid would include a row of three or more points, by the pigeonhole principle. The problem 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". Although the problem can be solved with points for every up to , it is conjectured that fewer than 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 points, not . 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 problem has applications in graph drawing and to the Heilbronn triangle problem. (Wikipedia).
