No-three-in-line problem
In mathematics, in the area of discrete geometry, the no-three-in-line problem 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. The problem was introduced by Henry Dudeney in 1917.
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
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), where k may be chosen arbitrarily as long as it is nonzero mod n/2. Again, for arbitrary n one can perform this construction for a prime near n/2 to obtain a solution with
points.
Guy & Kelly (1968) conjectured that for large n one cannot do better than c n with
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
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
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 . 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.
...
Wikipedia