No-three-in-line problem

The no-three-in-line problem in discrete geometry asks how many points can be placed in the

Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".

The problem was first posed by Henry Dudeney in 1900, as a puzzle in recreational mathematics, phrased in terms of placing the 16 pawns of a chessboard onto the board so that no three are in a line.

[3] In a later version of the puzzle, Dudeney modified the problem, making its solution unique, by asking for a solution in which two of the pawns are on squares d4 and e5, attacking each other in the center of the board.

[4] Many authors have published solutions to this problem for small values of

However, both proven and conjectured bounds limit this number to within a range proportional to

A solution of Paul Erdős, published by Roth (1951), is based on the observation that when

[7] Erdős' bound has been improved subsequently: Hall et al. (1975) show that, when

For, if more points are placed, then by the pigeonhole principle some three of them would all lie on the same horizontal line of the grid.

points can be placed on small grids, Guy & Kelly (1968) conjectured that for large grids, there is a significantly smaller upper bound on the number of points that can be placed.

More precisely, they conjectured that the number of points that can be placed is at most a sublinear amount larger than

Solutions to the no-three-in-line problem can be used to avoid certain kinds of degeneracies in graph drawing.

The problem they apply to involves placing the vertices of a given graph at integer coordinates in the plane, and drawing the edges of the graph as straight line segments.

The no-three-in-line drawing of a complete graph is a special case of this result with

within the unit square, with no three in a line, then by Pick's theorem every triangle would have area at least

Therefore, solving an instance of the no-three-in-line problem and then scaling down the integer grid to fit within a unit square produces solutions to the Heilbronn triangle problem where the smallest triangle has area

This application was the motivation for Paul Erdős to find his solution for the no-three-in-line problem.

[14] In computational geometry, finite sets of points with no three in line are said to be in general position.

In this terminology, the no-three-in-line problem seeks the largest subset of a grid that is in general position, but researchers have also considered the problem of finding the largest general position subset of other non-grid sets of points.

It is NP-hard to find this subset, for certain input sets, and hard to approximate its size to within a constant factor; this hardness of approximation result is summarized by saying that the problem is APX-hard.

[15] One can get a finer-grained understanding of the running time of algorithms for finding the exact optimal solution by using parameterized complexity, in which algorithms are analyzed not only in terms of the input size, but in terms of other parameters of the input.

In this case, for inputs whose largest general position subset has size

Problems with this kind of time bound are called fixed-parameter tractable.

, of size matching the existence bound, using an algorithmic technique known as entropy compression.

[15] Repeating a suggestion of Adena, Holton & Kelly (1974), Martin Gardner asked for the smallest subset of an

Equivalently, this is the smallest set that could be produced by a greedy algorithm that tries to solve the no-three-in-line problem by placing points one at a time until it gets stuck.

[18] However, less is known about the version of the problem where all lines are considered: every greedy placement includes at least

[19] Non-collinear sets of points in the three-dimensional grid were considered by Pór & Wood (2007).

[22] However, it does not work well to use this same idea of choosing points near a circle in two dimensions: this method finds points forming convex polygons, which satisfy the requirement of having no three in line, but are too small.

[25] When both dimensions are equal, and prime, it is not possible to place exactly one point in each row and column without forming a linear number of collinear triples.