Added to Favorites

Related Searches

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 2n, since if 2n + 1 points are placed in the grid some row will contain three points.
## Lower bounds

## Conjectured upper bounds

## Applications

## Generalizations

## Small values of n

## References

## External links

Paul Erdős (in Roth, 1951) 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

- (1 − ε)n

Erdős' bound has been improved subsequently: Hall et al (1975) 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

- (3/2 − ε)n

Guy and Kelly (1968) conjectured that one cannot do better, for large n, than cn with

- $c\; =\; sqrt[3]\{frac\{2pi^2\}\{3\}\}\; approx\; 1.874.$

- $c\; =\; frac\{pi\}\{sqrt\; 3\}\; approx\; 1.814.$

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

- $frac\{1-epsilon\}\{2n^2\}.$

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) x O(k) grid (Wood 2005).

Non-collinear sets of points in the three-dimensional grid were considered by Pór and Wood (2007). They proved that the maximum number of points in the n x n x n grid with no three points collinear is $Theta(n^2)$. 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 (Pach et al 1998; Dujmović et al 2005; Di Giacomo 2005).

For n ≤ 32, it is known that 2n 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

*

*

*

*

*

*

*

*

*

*

*

*

- Flammenkamp, Achim The No-Three-in-Line Problem. .

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 17:28:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Sunday October 05, 2008 at 17:28:35 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2014 Dictionary.com, LLC. All rights reserved.