No-three-in-line problem

A set of 20 points in a 10 × 10 grid, with no three points in a line.

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, then by the pigeonhole principle some row and some column will contain three points.

Lower bounds

Paul Erdős (in Roth 1951) observed that, when n is a prime number, the set of n grid points (i, i2 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 - \epsilon)n

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

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

(\frac{3}{2} - \epsilon)n

points.

Conjectured upper bounds

Guy & Kelly (1968) conjectured that for large n one cannot do better than c n with

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

Pegg, Jr. (2005) 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

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

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

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

Generalizations

Higher dimensions

Non-collinear sets of points in the three-dimensional grid were considered by Pór & Wood (2007). They proved that the maximum number of points in the n × n × n grid with no three points collinear is \Theta(n^2). Similarly to Erdős's 2D construction, this can be accomplished by using points (x, y, x2 + y2) mod p, where p is a prime congruent to 3 mod 4.

Another analogue in higher dimensions is to find sets of points that do not all lie in the same plane (or hyperplane). For the no-four-coplanar problem in three dimensions, it was reported by Ed Pegg, Oleg567 et al, that 8 such points can be selected in a 3x3x3 grid (exactly one solution up to rotation/reflection), 10 such points can be found for 4x4x4 (232 different solutions), and 13 such points can be found for 5x5x5 (38 different solutions).[1][2] As of 2015, it is not known what the maximal solution is for 6x6x6 grid, or how many such solutions exist. Similar to the 2n upper bound for the 2D case, there exists a 3n upper bound for the 3D case (no more than 3 points per plane, and no more than n such planes in the grid), though as seen above, not all values of n attain the upper bound.

Graph 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 (Wood (2005)).

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, Thiele & Tóth (1998); Dujmović, Morin & Wood (2005); Di Giacomo, Liotta & Meijer (2005)).

Small values of n

For n ≤ 46, 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

1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (sequence A000769 in OEIS).

Notes

  1. ↑ Ed Pegg's question
  2. ↑ Ed Pegg's site

References

External links

This article is issued from Wikipedia - version of the Tuesday, November 24, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.