No-three-in-line problem

Unsolved problem in mathematics:
How many points can be placed in an n-by-n grid so that no three of them lie on a line?
<a href="/facts/List_of_unsolved_problems_in_mathematics/RroxGPpP">(more unsolved problems in mathematics)</a>

The no-three-in-line problem in <a href="/facts/Discrete_geometry/Ixnl3GBc">discrete geometry</a> asks how many points can be placed in the 
 
 
 
 n
 ×
 n
 
 
 {\displaystyle n\times n}
 
 grid so that no three points lie on the same line. The problem concerns lines of all <a href="/facts/Slope/a2L3k0j5">slopes</a>, not only those aligned with the grid. It was introduced by <a href="/facts/Henry_Dudeney/YSSBQgoK">Henry Dudeney</a> in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".
At most 
 
 
 
 2
 n
 
 
 {\displaystyle 2n}
 
 points can be placed, because 
 
 
 
 2
 n
 +
 1
 
 
 {\displaystyle 2n+1}
 
 points in a grid would include a row of three or more points, by the <a href="/facts/Pigeonhole_principle/hDks9p4n">pigeonhole principle</a>. Although the problem can be solved with 
 
 
 
 2
 n
 
 
 {\displaystyle 2n}
 
 points for every 
 
 
 
 n
 
 
 {\displaystyle n}
 
 up to 
 
 
 
 46
 
 
 {\displaystyle 46}
 
, it is conjectured that fewer than 
 
 
 
 2
 n
 
 
 {\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 
 
 
 
 1.5
 n
 
 
 {\displaystyle 1.5n}
 
 points, not 
 
 
 
 2
 n
 
 
 {\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 <a href="/facts/Recreational_mathematics/p2b8zl2J">recreational mathematics</a>, the no-three-in-line problem has applications in <a href="/facts/Graph_drawing/uhh73BVo">graph drawing</a> and to the <a href="/facts/Heilbronn_triangle_problem/tC5soztj">Heilbronn triangle problem</a>.

No-three-in-line problem open-in-new

No-three-in-line problem