# No-three-in-line problem

In mathematics, in the area of discrete geometry, the **no-three-in-line**-problem, introduced by Henry Dudeney in 1917, asks for the maximum number of points that can be placed in the *n* × *n* grid so that no three points are collinear. This number is at most 2*n*, since if 2*n* + 1 points are placed in the grid some row will contain three points.

## Lower bounds

Paul Erdős (in Template:Harvnb) observed that, when *n* is a prime number, the set of *n* grid points (*i*, *i*^{2} mod *n*), for 0 ≤ *i* < *n*, contains no three collinear points. When *n* is not prime, one can perform this construction for a *p* × *p* grid contained in the *n* × *n* grid, where *p* is the largest prime that is at most *n*. As a consequence, for any ε and any sufficiently large *n*, one can place

points in the *n* × *n* grid with no three points collinear.

Erdős' bound has been improved subsequently: Template:Harvtxt show that, when *n*/2 is prime, one can obtain a solution with 3(*n* - 2)/2 points by placing points on the hyperbola *xy* ≡ *k* (mod *n*/2) for a suitable *k*. Again, for arbitrary *n* one can perform this construction for a prime near *n*/2 to obtain a solution with

points.

## Conjectured upper bounds

Template:Harvtxt conjectured that for large *n* one cannot do better than *c n* with

Template:Harvtxt noted that Gabor Ellmann found, in March 2004, an error in the original paper of Guy and Kelly's heuristic reasoning, which if corrected, results in

## Applications

The Heilbronn triangle problem asks for the placement of *n* points in a unit square that maximizes the area of the smallest triangle formed by three of the points. By applying Erdős' construction of a set of grid points with no three collinear points, one can find a placement in which the smallest triangle has area

## Generalizations

A noncollinear placement of *n* points can also be interpreted as a graph drawing of the complete graph in such a way that, although edges cross, no edge passes through a vertex. Erdős' construction above can be generalized to show that every *n*-vertex *k*-colorable graph has such a drawing in a *O*(*n*) × *O*(*k*) grid (Template:Harvtxt).

Non-collinear sets of points in the three-dimensional grid were considered by Template:Harvtxt. They proved that the maximum number of points in the *n* × *n* × *n* grid with no three points collinear is .
Similarly to Erdős's 2D construction, this can be accomplished by using points
(*x*, *y*, *x*^{2} + *y*^{2}) mod *p*, where *p* is a prime congruent to 3 mod 4.
One can also consider graph drawings in the three-dimensional grid. Here the non-collinearity condition means that a vertex should not lie on a non-adjacent edge, but it is normal to work with the stronger requirement that no two edges cross (Template:Harvtxt; Template:Harvtxt; Template:Harvtxt).

## Small values of *n*

For *n* ≤ 46, it is known that 2*n* points may be placed with no three in a line. The numbers of solutions (not counting reflections and rotations as distinct) for small *n* = 2, 3, ..., are

## References

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:citation/CS1|citation

|CitationClass=conference }}

- {{#invoke:citation/CS1|citation

|CitationClass=conference }}

- Template:Cite web
- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}

- {{#invoke:citation/CS1|citation

|CitationClass=citation }}

- {{#invoke:Citation/CS1|citation

|CitationClass=journal }}