No-three-in-line problem

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

The no-three-in-line problem in discrete geometry asks how many points can be placed in the $n \times n$ grid so that no three points lie on the same line. This number is at most $2 n$ , because $2 n + 1$ points in a grid would include a row of three or more points, by the pigeonhole principle. The problem was introduced by Henry Dudeney in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".^[1]

Although the problem can be solved with $2 n$ points for every $n$ up to $46$ , it is conjectured that fewer than $2 n$ points can be placed in grids of large size. Known methods can place linearly many points in grids of arbitrary size, but the best of these methods place slightly fewer than $3 n /2$ points, not $2 n$ . Several related problems of finding points with no three in line, among other sets of points than grids, have also been studied.

Although originating in recreational mathematics, the problem has applications in graph drawing and to the Heilbronn triangle problem.

Small instances

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.^[2] This is exactly the no-three-in-line problem, for the case $n=8$ .^[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 $n$ ,^[5] and by 1998 it was known that $2 n$ points could be placed on an $n \times n$ grid with no three in a line for all $n$ up to 46, and some larger values.^[6] The numbers of solutions (not counting reflections and rotations as distinct) for small $n = 2, 3, ...,$ are^[3]^[7]

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

Upper and lower bounds

The exact number of points that can be placed, as a function of $n$ , is not known. However, both proven and conjectured bounds limit this number to within a range proportional to $n$ .

General placement methods

Suboptimal placement of $11$ points in $12\times 12$ grid, using the method of Erdős. The largest prime $p$ less than the grid size is $p=11$ ; the solution places points at coordinates $(i,i^{2}$ mod $p)$ for $i=0,1,\dots p-1$ . For instance, $(4,5)$ is included because $4^{2}=16\cong 5$ $($ mod $11)$ .

A solution of Paul Erdős, published by Roth (1951), is based on the observation that when $n$ is a prime number, the set of $n$ grid points $(i, i 2 mod n)$ , for $0 \leq i < n$ , contains no three collinear points. When $n$ is not prime, one can perform this construction for a $p \times p$ grid contained in the $n \times 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-\varepsilon )n$ points in the $n \times n$ grid with no three points collinear.^[8]

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 \equiv 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 $\left({\frac {3}{2}}-\varepsilon \right)n$ points.^[9]

Upper bound

At most $2 n$ points may be placed in a grid of any size $n$ . 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. For small-enough values of $n$ , this trivial bound is tight.^[3]

Conjectured bounds

Although exactly $2 n$ 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 $cn$ , with^[10] $c={\sqrt[{3}]{\frac {2\pi ^{2}}{3}}}\approx 1.874.$ After an error in the heuristic reasoning leading to this conjecture was uncovered, Guy corrected the error and made the stronger conjecture that one cannot do more than sublinearly better than $cn$ with^[11] $c={\frac {\pi }{\sqrt {3}}}\approx 1.814.$

Applications

In graph drawing, solutions to the no-three-in-line problem can be used to place the vertices of a graph so that, when drawn as straight line segments, no edge passes through a vertex that is not its endpoint.^[12] In particular, this applies to drawings of complete graphs, which can be drawn in this way using a grid whose area is quadratic in the number of vertices, optimal for any grid drawing. More generally, if a graph has $n$ vertices and a graph coloring with $k$ colors, it can be drawn in a grid with area proportional to $nk$ ; the no-three-in-line drawing of a complete graph is a special case of this result with $k = n$ .^[13]

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. A triangle with integer coordinates has area at least ${\tfrac {1}{2}}$ by Pick's theorem, and scaling the integer grid down so that an $n\times n$ grid fits within the unit square reduces this area by a quadratic factor. Therefore, the constructions for linearly many points with no three in line lead to solutions to the Heilbronn triangle problem in which the smallest area is at least proportional to $1/k^{2}$ . This application was the motivation for Paul Erdős to find his solution for the no-three-in-line problem.^[14] It remained the best area lower bound known for the Heilbronn triangle problem from 1951 until 1982, when it was improved by a logarithmic factor using a construction that was not based on the no-three-in-line problem.^[15]

Generalizations and variations

General-position subsets

The no-three-in-line problem is an instance of a more general problem in computational geometry, of finding the largest subset of points in general position (no three in line) in an arbitrary set $S$ of points. This problem is NP-hard, and hard to approximate (APX-hard). If the largest subset has size $k$ , a solution with approximation ratio $O({\sqrt {k}})$ can be obtained by a greedy algorithm that simply chooses points one at a time until all remaining points lie on lines through pairs of chosen points. The problem is also fixed-parameter tractable, having an algorithm whose time is exponential in $k$ but polynomial in the input size.^[16] For point sets having at most ${\textstyle \ell }$ points per line, with ${\textstyle \ell =O({\sqrt {|S|}})}$ , there exist general-position subsets of size nearly proportional to ${\textstyle \ell =O({\sqrt {|S|}})}$ ; the example of the grid shows that this bound cannot be significantly improved.^[17] The proof of existence of these large general-position subsets can be converted into a polynomial-time algorithm using entropy compression.^[18]

Greedy placement

Repeating a suggestion of Adena, Holton & Kelly (1974), Martin Gardner asked for the smallest subset of an $n \times n$ grid that cannot be extended: it has no three points in a line, but every proper superset has three in a line. 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.^[3] If only axis-parallel and diagonal lines are considered, then every such set has at least $n - 1$ points.^[19] However, less is known about the version of the problem where all lines are considered: every greedy placement includes at least $\Omega (n^{2/3})$ points before getting stuck, but nothing better than the trivial $2n$ upper bound is known.^[20]

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 \times n \times 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, x 2 + y 2) mod p$ , where $p$ is a prime congruent to $3 mod 4$ .^[21] Just as the original no-three-in-line problem can be used for two-dimensional graph drawing, 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.^[22]

In even higher dimensions, grid points with no three in line, obtained by taking the points between two spherical shells, have been used for finding large Salem–Spencer sets, sets of integers with no three forming an arithmetic progression.^[23] However, a similar idea of placing points in a convex polygon does not work well for the two-dimensional no-three-in-line problem, as the largest convex polygons with vertices in an $n \times n$ grid have only $O (n 2/3)$ vertices.^[24] The cap set problem concerns a similar problem in high-dimensional vector spaces over finite fields.^[25]

Torus

Another variation on the problem involves converting the grid into a discrete torus by using periodic boundary conditions in which the left side of the torus is connected to the right side, and the top side is connected to the bottom side. This has the effect, on slanted lines through the grid, of connecting them up into longer lines through more points, and therefore making it more difficult to select points with at most two from each line. These extended lines can also be interpreted as normal lines through an infinite grid in the Euclidean plane, taken modulo the dimensions of the torus. For a torus based on an $m\times n$ grid, the maximum number of points that can be chosen with no three in line is at most $2\gcd(m,n)$ .^[26] 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.^[27] Higher-dimensional torus versions of the problem have also been studied.^[28]

Notes

^ Brass, Moser & Pach 2005.
^ The Weekly Dispatch, April 29 and May 13, 1900, as cited by Knuth 2008.
^ ^a ^b ^c ^d Gardner 1976.
^ Dudeney 1917.
^ Craggs & Hughes-Jones 1976; Kløve 1978, 1979; Anderson 1979; Harborth, Oertel & Prellberg 1989; Flammenkamp 1992, 1998.
^ Flammenkamp 1998.
^ Sloane, N. J. A. (ed.). "Sequence A000769". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.
^ Erdős did not publish this observation; it appears in Roth 1951.
^ Hall et al. 1975.
^ Guy & Kelly 1968.
^ As reported by Pegg 2005. The discovery of this error was credited by Pegg to Gabor Ellmann.
^ Brass et al. 2007.
^ Wood 2005.
^ Roth 1951.
^ Komlós, Pintz & Szemerédi 1982.
^ Froese et al. 2017; Eppstein 2018
^ Payne & Wood 2013.
^ Eppstein 2018.
^ Cooper et al. 2014.
^ Aichholzer, Eppstein & Hainzl (2021).
^ Pór & Wood 2007.
^ Pach, Thiele & Tóth 1998; Dujmović, Morin & Wood 2005; Di Giacomo, Liotta & Meijer 2005
^ Elkin 2011.
^ Jarník 1926.
^ Klarreich 2016.
^ Misiak et al. 2016.
^ Cooper & Solymosi 2005.
^ Ku & Wong 2018.

References

Adena, Michael A.; Holton, Derek A.; Kelly, Patrick A. (1974). "Some thoughts on the no-three-in-line problem". In Holton, Derek A. (ed.). Combinatorial Mathematics: Proceedings of the Second Australian Conference (University of Melbourne, 1973). Lecture Notes in Mathematics. Vol. 403. pp. 6–17. doi:10.1007/BFb0057371. MR 0349396.
Aichholzer, Oswin; Eppstein, David; Hainzl, Eva-Maria (April 2021), "Geometric dominating sets – a minimum version of the no-three-in-line problem", Book of Abstracts: 37th European Workshop on Computational Geometry, Saint-Petersburg University, pp. 17:1–17:7
Anderson, David Brent (1979). "Update on the no-three-in-line problem". Journal of Combinatorial Theory. Series A. 27 (3): 365–366. doi:10.1016/0097-3165(79)90025-6. MR 0555806.
Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.; Lubiw, Anna; Mitchell, Joseph S. B. (2007). "On simultaneous planar graph embeddings". Computational Geometry. 36 (2): 117–130. doi:10.1016/j.comgeo.2006.05.006. MR 2278011.
Brass, Peter; Moser, William; Pach, János (2005). "Section 10.1: Packing lattice points in subspaces". Research Problems in Discrete Geometry. Springer, New York. pp. 417–421. ISBN 978-0-387-29929-7. MR 2163782.
Cooper, Alec S.; Pikhurko, Oleg; Schmitt, John R.; Warrington, Gregory S. (2014). "Martin Gardner's minimum no-3-in-a-line problem". American Mathematical Monthly. 121 (3): 213–221. arXiv:1206.5350. doi:10.4169/amer.math.monthly.121.03.213. JSTOR 10.4169/amer.math.monthly.121.03.213.
Cooper, Joshua N.; Solymosi, József (2005). "Collinear points in permutations" (PDF). Annals of Combinatorics. 9 (2): 169–175. arXiv:math/0408396. doi:10.1007/s00026-005-0248-4. MR 2153735.
Craggs, D.; Hughes-Jones, R. (1976). "On the no-three-in-line problem". Journal of Combinatorial Theory. Series A. 20 (3): 363–364. doi:10.1016/0097-3165(76)90030-3. MR 0406804.
Dudeney, Henry (1917). "317. A puzzle with pawns". Amusements in Mathematics. Edinburgh: Nelson. p. 94. Solution, p. 222. Originally published in the London Tribune, November 7, 1906.
Di Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). "Computing straight-line 3d grid drawings of graphs in linear volume". Computational Geometry: Theory and Applications. 32 (1): 26–58. doi:10.1016/j.comgeo.2004.11.003.
Dujmović, Vida; Morin, Pat; Wood, David R. (2005). "Layout of graphs with bounded tree-width". SIAM Journal on Computing. 34 (3): 553–579. arXiv:cs/0406024. doi:10.1137/S0097539702416141. S2CID 3264071.
Elkin, Michael (2011). "An improved construction of progression-free sets". Israel Journal of Mathematics. 184: 93–128. arXiv:0801.4310. doi:10.1007/s11856-011-0061-1. MR 2823971.
Eppstein, David (2018). "Chapter 9: General position". Forbidden Configurations in Discrete Geometry. Cambridge University Press. pp. 72–86.
Felsner, Stefan; Liotta, Giuseppe; Wismath, Stephen K. (2003). "Straight-line drawings on restricted integer grids in two and three dimensions". Journal of Graph Algorithms and Applications. 7 (4): 363–398. doi:10.7155/jgaa.00075.
Flammenkamp, Achim (1992). "Progress in the no-three-in-line problem". Journal of Combinatorial Theory. Series A. 60 (2): 305–311. doi:10.1016/0097-3165(92)90012-J.
Flammenkamp, Achim (1998). "Progress in the no-three-in-line problem, II". Journal of Combinatorial Theory. Series A. 81 (1): 108–113. doi:10.1006/jcta.1997.2829.
Froese, Vincent; Kanj, Iyad; Nichterlein, André; Niedermeier, Rolf (2017). "Finding points in general position". International Journal of Computational Geometry & Applications. 27 (4): 277–296. arXiv:1508.01097. doi:10.1142/S021819591750008X. MR 3766097.
Gardner, Martin (October 1976). "Combinatorial problems, some old, some new and all newly attacked by computer". Mathematical Games. Scientific American. Vol. 235, no. 4. pp. 131–137. JSTOR 24950467.
Guy, R. K.; Kelly, P. A. (1968). "The no-three-in-line problem". Canadian Mathematical Bulletin. 11 (4): 527–531. doi:10.4153/CMB-1968-062-3. MR 0238765.
Hall, R. R.; Jackson, T. H.; Sudbery, A.; Wild, K. (1975). "Some advances in the no-three-in-line problem". Journal of Combinatorial Theory. Series A. 18 (3): 336–341. doi:10.1016/0097-3165(75)90043-6.
Harborth, Heiko; Oertel, Philipp; Prellberg, Thomas (1989). "No-three-in-line for seventeen and nineteen". Proceedings of the Oberwolfach Meeting “Kombinatorik” (1986). Discrete Mathematics. 73 (1–2): 89–90. doi:10.1016/0012-365X(88)90135-5. MR 0974815.
Jarník, Vojtěch (1926). "Über die Gitterpunkte auf konvexen Kurven" [On the grid points on convex curves]. Mathematische Zeitschrift (in German). 24 (1): 500–518. doi:10.1007/BF01216795. MR 1544776.
Klarreich, Erica (May 31, 2016). "Simple Set Game Proof Stuns Mathematicians". Quanta.
Kløve, Torleiv (1978). "On the no-three-in-line problem. II". Journal of Combinatorial Theory. Series A. 24 (1): 126–127. doi:10.1016/0097-3165(78)90053-5. MR 0462998.
Kløve, Torleiv (1979). "On the no-three-in-line problem. III". Journal of Combinatorial Theory. Series A. 26 (1): 82–83. doi:10.1016/0097-3165(79)90055-4. MR 0525088.
Komlós, J.; Pintz, J.; Szemerédi, E. (1982). "A lower bound for Heilbronn's problem". Journal of the London Mathematical Society. 25 (1): 13–24. doi:10.1112/jlms/s2-25.1.13. MR 0645860.
Knuth, Donald E. (2008). "Answer to exercise 242". The Art of Computer Programming, Fascicle 1b: A Draft of Section 7.1.4: Binary Decision Diagrams. p. 130.
Ku, Cheng Yeaw; Wong, Kok Bin (2018). "On no-three-in-line problem on $m$ -dimensional torus". Graphs and Combinatorics. 34 (2): 355–364. doi:10.1007/s00373-018-1878-8. MR 3774457.
Lefmann, Hanno (2008). "No $l$ grid-points in spaces of small dimension". Algorithmic Aspects in Information and Management, 4th International Conference, AAIM 2008, Shanghai, China, June 23–25, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5034. Springer-Verlag. pp. 259–270. doi:10.1007/978-3-540-68880-8_25.
Misiak, Aleksander; Stępień, Zofia; Szymaszkiewicz, Alicja; Szymaszkiewicz, Lucjan; Zwierzchowski, Maciej (2016). "A note on the no-three-in-line problem on a torus". Discrete Mathematics. 339 (1): 217–221. arXiv:1406.6713. doi:10.1016/j.disc.2015.08.006. MR 3404483.
Pach, János; Thiele, Torsten; Tóth, Géza (1998). "Three-dimensional grid drawings of graphs". Graph Drawing, 5th Int. Symp., GD '97. Lecture Notes in Computer Science. Vol. 1353. Springer-Verlag. pp. 47–51. doi:10.1007/3-540-63938-1_49.
Payne, Michael S.; Wood, David R. (2013). "On the general position subset selection problem". SIAM Journal on Discrete Mathematics. 27 (4): 1727–1733. arXiv:1208.5289. doi:10.1137/120897493. MR 3111653.
Pegg, Ed Jr. (April 11, 2005). "Chessboard Tasks". Math Games. Mathematical Association of America. Retrieved June 25, 2012.
Pór, Attila; Wood, David R. (2007). "No-three-in-line-in-3D". Algorithmica. 47 (4): 481. doi:10.1007/s00453-006-0158-9. S2CID 209841346.
Roth, K. F. (1951). "On a problem of Heilbronn". Journal of the London Mathematical Society. 26 (3): 198–204. doi:10.1112/jlms/s1-26.3.198.
Wood, David R. (2005). "Grid drawings of $k$ -colourable graphs". Computational Geometry: Theory and Applications. 30 (1): 25–28. doi:10.1016/j.comgeo.2004.06.001.

External links

Flammenkamp, Achim. "The No-Three-in-Line Problem".
Weisstein, Eric W. "No-Three-in-a-Line-Problem". MathWorld.

[FOOTNOTEBrassMoserPach2005-1] Brass, Moser & Pach 2005.

[2] The Weekly Dispatch, April 29 and May 13, 1900, as cited by Knuth 2008.

[FOOTNOTEGardner1976-3] Gardner 1976.

[FOOTNOTEDudeney1917-4] Dudeney 1917.

[5] Craggs & Hughes-Jones 1976; Kløve 1978, 1979; Anderson 1979; Harborth, Oertel & Prellberg 1989; Flammenkamp 1992, 1998.

[FOOTNOTEFlammenkamp1998-6] Flammenkamp 1998.

[7] Sloane, N. J. A. (ed.). "Sequence A000769". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.

[8] Erdős did not publish this observation; it appears in Roth 1951.

[FOOTNOTEHallJacksonSudberyWild1975-9] Hall et al. 1975.

[FOOTNOTEGuyKelly1968-10] Guy & Kelly 1968.

[11] As reported by Pegg 2005. The discovery of this error was credited by Pegg to Gabor Ellmann.

[FOOTNOTEBrassCenekDuncanEfrat2007-12] Brass et al. 2007.

[FOOTNOTEWood2005-13] Wood 2005.

[FOOTNOTERoth1951-14] Roth 1951.

[FOOTNOTEKomlósPintzSzemerédi1982-15] Komlós, Pintz & Szemerédi 1982.

[16] Froese et al. 2017; Eppstein 2018

[FOOTNOTEPayneWood2013-17] Payne & Wood 2013.

[FOOTNOTEEppstein2018-18] Eppstein 2018.

[FOOTNOTECooperPikhurkoSchmittWarrington2014-19] Cooper et al. 2014.

[FOOTNOTEAichholzerEppsteinHainzl2021-20] Aichholzer, Eppstein & Hainzl (2021).

[FOOTNOTEPórWood2007-21] Pór & Wood 2007.

[22] Pach, Thiele & Tóth 1998; Dujmović, Morin & Wood 2005; Di Giacomo, Liotta & Meijer 2005

[FOOTNOTEElkin2011-23] Elkin 2011.

[FOOTNOTEJarník1926-24] Jarník 1926.

[FOOTNOTEKlarreich2016-25] Klarreich 2016.

[FOOTNOTEMisiakStępieńSzymaszkiewiczSzymaszkiewicz2016-26] Misiak et al. 2016.

[FOOTNOTECooperSolymosi2005-27] Cooper & Solymosi 2005.

[FOOTNOTEKuWong2018-28] Ku & Wong 2018.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]