View source for No-three-in-line problem

{{good article}}
{{Short description|Geometry problem on grid points}}
{{unsolved|mathematics|How many points can be placed in an ''n''-by-''n'' grid so that no three of them lie on a line?}}
[[Image:No-three-in-line.svg|thumb|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 <math>n\times n</math> grid so that no three points lie on the same line. The problem concerns lines of all [[slope]]s, not only those aligned with the grid. It 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".{{sfn|Brass|Moser|Pach|2005}}

At most <math>2n</math> points can be placed, because <math>2n+1</math> points in a grid would include a row of three or more points, by the [[pigeonhole principle]]. Although the problem can be solved with <math>2n</math> points for every <math>n</math> up {{nowrap|to <math>46</math>,}} it is conjectured that fewer than <math>2n</math> 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 <math>1.5n</math> points, {{nowrap|not <math>2n</math>.}}

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 no-three-in-line problem has applications in [[graph drawing]] and to the [[Heilbronn triangle problem]].

{{Clear}}

==Small instances==
{{Chess diagram
| tright
|
| numbers = neither
| letters = neither

|  |  |pl|  |  |  |pl|  
|  |  |pl|  |pl|  |  |  
|pl|pl|  |  |  |  |  |  
|  |  |  |  |pl|  |pl|  
|  |pl|  |pl|  |  |  |  
|  |  |  |  |  |pl|  |pl
|pl|  |  |pl|  |  |  |  
|  |  |  |  |  |pl|  |pl

|Solution to Dudeney's puzzle of placing 16 pawns on a chessboard such that no three pawns lie on the same line, with two pawns on squares d4 and e5.
}}
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.<ref>''The Weekly Dispatch'', April 29 and May 13, 1900, as cited by {{harvnb|Knuth|2008}}.</ref> This is exactly the no-three-in-line problem, for the {{nowrap|case <math>n=8</math>.{{sfn|Gardner|1976}}}} 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 [[Algebraic notation (chess)|squares d4 and e5]], attacking each other in the center of the board.{{sfn|Dudeney|1917}}

Many authors have published solutions to this problem for small values {{nowrap|of <math>n</math>,<ref>{{harvnb|Craggs|Hughes-Jones|1976}}; {{harvs|last=Kløve|year1=1978|year2=1979|nb}}; {{harvnb|Anderson|1979}}; {{harvnb|Harborth|Oertel|Prellberg|1989}}; {{harvs|last=Flammenkamp|year1=1992|year2=1998|nb}}.</ref>}} and by 1998 it was known that <math>2n</math> points could be placed on an <math>n\times n</math> grid with no three in a line
for all <math>n</math> up {{nowrap|to 46,}} and some larger values.<ref>{{harvs|last=Flammenkamp|year1=1992|year2=1998|nb}}.</ref> The numbers of solutions with <math>2n</math> points for small values of <math>n</math>, starting {{nowrap|from <math>n=2</math>,}} are
{{bi|left=1.6|1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... {{OEIS|A000755}}.}}
The numbers of equivalence classes of solutions with <math>2n</math> points under reflections and rotations are
{{bi|left=1.6|1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... {{OEIS|A000769}}.{{sfn|Gardner|1976}}}}{{Clear}}

==Upper and lower bounds==
The exact number of points that can be placed, as a function {{nowrap|of <math>n</math>,}} is not known. However, both proven and conjectured bounds limit this number to within a range proportional {{nowrap|to <math>n</math>.}}

===General placement methods===
[[File:Erdős-no-3-in-line-12x12.svg|thumb|upright=1.5|Suboptimal placement of <math>11</math> points in <math>12\times 12</math> grid, using the method of Erdős. The largest prime <math>p</math> less than the grid size is {{nowrap|<math>p=11</math>;}} the solution places points at coordinates {{nowrap|<math>(i,i^2</math> mod <math>p)</math>}} for {{nowrap|<math>i=0,1,\dots p-1</math>.}} For instance, <math>(4,5)</math> is included because <math>4^2=16\cong 5</math> {{nowrap|(<math></math>mod <math>11</math>).}}]]
A solution of [[Paul Erdős]], published by {{harvtxt|Roth|1951}}, is based on the observation that when <math>n</math> is a [[prime number]], the set of <math>n</math> grid points {{nowrap|<math>(i,i^2</math> mod <math>n)</math>,}} for {{nowrap|<math>0\le i < n</math>,}} contains no three collinear points. When <math>n</math> is not prime, one can perform this construction for a <math>p\times p</math> grid contained in the <math>n\times n</math> grid, where <math>p</math> is the largest prime that is at {{nowrap|most <math>n</math>.}} Because the [[Prime gap|gap between consecutive primes]] is much smaller than the primes themselves, <math>p</math> will always be close {{nowrap|to <math>n</math>,}} so this method can be used to place <math>n-o(n)</math> points in the <math>n\times n</math> grid with no three points collinear.<ref>Erdős did not publish this observation; it appears in {{harvnb|Roth|1951}}.</ref>

Erdős' bound has been improved subsequently: {{harvtxt|Hall|Jackson|Sudbery|Wild|1975}} show that, when <math>n/2</math> is prime, one can obtain a solution with <math>3(n-2)/2</math> points, by placing points in multiple copies of the [[hyperbola]] <math>xy=k</math> {{nowrap|(mod <math>n/2</math>),}} where <math>k</math> may be chosen arbitrarily as long as it is nonzero {{nowrap|mod <math>n/2</math>.}} Again, for arbitrary <math>n</math> one can perform this construction for a prime near <math>n/2</math> to obtain a solution with
{{nowrap|<math>\tfrac32n-o(n)</math> points.{{sfn|Hall|Jackson|Sudbery|Wild|1975}}}}

===Upper bound===
At most <math>2n</math> points may be placed in a grid of any {{nowrap|size <math>n</math>.}} 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 <math>n\leq 46</math>, this trivial bound is known to be tight.{{sfn|Gardner|1976}}

===Conjectured bounds===
Although exactly <math>2n</math> points can be placed on small grids, {{harvtxt|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 {{nowrap|than <math>cn</math>,}} with{{sfn|Guy|Kelly|1968}}
<math display=block>c = \sqrt[3]{\frac{2\pi^2}{3}} \approx 1.874.</math>
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 <math>cn</math> with<ref>As reported by {{harvnb|Pegg|2005}}. The discovery of this error was credited by Pegg to Gabor Ellmann.</ref>
<math display=block>c = \frac{\pi}{\sqrt 3} \approx 1.814.</math>

==Applications==
Solutions to the no-three-in-line problem can be used to avoid certain kinds of [[degeneracy (mathematics)|degeneracies]] in [[graph drawing]]. The problem they apply to involves placing the [[vertex (graph theory)|vertices]] of a given graph at integer coordinates in the plane, and drawing the [[edge (graph theory)|edges]] of the graph as straight [[line segment]]s. For certain graphs, such as the [[utility graph]], crossings between pairs of edges are unavoidable, but one should still avoid placements that cause a vertex to lie on an edge through two other vertices. When the vertices are placed with no three in line, this kind of problematic placement cannot occur, because the entire line through any two vertices, and not just the line segment, is free of other vertices.{{sfn|Brass|Cenek|Duncan|Efrat|2007}} The fact that the no-three-in-line problem has a solution with linearly many points can be translated into graph drawing terms as meaning that every graph, even a [[complete graph]], can be drawn without unwanted vertex-edge incidences using a grid whose area is quadratic in the number of vertices, and that for complete graphs no such drawing with less than quadratic area is possible. The complete graphs also require a linear number of colors in any [[graph coloring]], but other graphs that can be colored with fewer colors can also be drawn on smaller grids: if a graph has <math>n</math> vertices and a [[graph coloring]] with <math>k</math> colors, it can be drawn in a grid with area proportional {{nowrap|to <math>nk</math>.}} The no-three-in-line drawing of a complete graph is a special case of this result {{nowrap|with <math>k=n</math>.{{sfn|Wood|2005}}}}

The no-three-in-line problem also has applications to another problem in discrete geometry, the [[Heilbronn triangle problem]]. In this problem, one must place <math>n</math> points, anywhere in a unit square, not restricted to a grid. The goal of the placement is to avoid small-area triangles, and more specifically to maximize the area of the smallest triangle formed by three of the points. For instance, a placement with three points in line would be very bad by this criterion, because these three points would form a degenerate triangle with area zero. On the other hand, if the points can be placed on a grid of side length <math>\varepsilon</math> within the unit square, with no three in a line, then by [[Pick's theorem]] every triangle would have area at {{nowrap|least <math>\varepsilon^2/2</math>,}} half of a grid square. 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 {{nowrap|<math>\Omega(1/n^2)</math>.}} This application was the motivation for Paul Erdős to find his solution for the no-three-in-line problem.{{sfn|Roth|1951}} 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.{{sfn|Komlós|Pintz|Szemerédi|1982}}

==Generalizations and variations==
===General-position subsets===
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 [[approximation algorithm|approximate]] its size to within a constant factor; this hardness of approximation result is summarized by saying that the problem is [[APX-hard]]. If the largest subset has {{nowrap|size <math>k</math>,}} a solution with the non-constant [[approximation ratio]] <math>O(\sqrt k)</math> 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.{{sfn|Eppstein|2018}}

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 {{nowrap|size <math>k</math>,}} it can be found in an amount of time that is an exponential function of <math>k</math> multiplied by a polynomial in the input {{nowrap|size <math>n</math>,}} with the exponent of the polynomial not depending {{nowrap|on <math>k</math>.}} Problems with this kind of time bound are called [[fixed-parameter tractable]].<ref>{{harvnb|Froese|Kanj|Nichterlein|Niedermeier|2017}}; {{harvnb|Eppstein|2018}}</ref>

For point sets <math>S</math> having at most <math display=inline>\ell</math> points per line, with {{nowrap|<math display=inline>\ell=O(\sqrt{|S|})</math>,}} there exist general-position subsets of size nearly proportional {{nowrap|to <math display=inline>\ell=O(\sqrt{|S|})</math>.}} The example of the grid shows that this bound cannot be significantly improved.{{sfn|Payne|Wood|2013}} The proof of existence of these large general-position subsets can be converted into a [[polynomial-time]] algorithm for finding a general-position subset {{nowrap|of <math>S</math>,}} of size matching the existence bound, using an algorithmic technique known as [[entropy compression]].{{sfn|Eppstein|2018}}

===Greedy placement===
Repeating a suggestion of {{harvtxt|Adena|Holton|Kelly|1974}}, [[Martin Gardner]] asked for the smallest subset of an <math>n\times n</math> 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.{{sfn|Gardner|1976}} If only axis-parallel and diagonal lines are considered, then every such set has at least <math>n-1</math> points.{{sfn|Cooper|Pikhurko|Schmitt|Warrington|2014}} However, less is known about the version of the problem where all lines are considered: every greedy placement includes at least <math>\Omega(n^{2/3})</math> points before getting stuck, but nothing better than the trivial <math>2n</math> upper bound is known.{{sfnp|Aichholzer|Eppstein|Hainzl|2023}}

===Higher dimensions===
Non-collinear sets of points in the three-dimensional grid were considered by {{harvtxt|Pór|Wood|2007}}. They proved that the maximum number of points in the <math>n\times n\times n</math> grid with no three points collinear {{nowrap|is <math>\Theta(n^2)</math>.}} 
Similarly to Erdős's 2D construction, this can be accomplished by using points {{nowrap|<math>(x,y,x^2+y^2</math> mod <math>p)</math>,}} where <math>p</math> is a prime congruent to {{nowrap|3 mod 4}}.{{sfn|Pór|Wood|2007}}
Just as the original no-three-in-line problem can be used for two-dimensional graph drawing, one can use this three-dimensional solution to draw graphs 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.<ref>{{harvnb|Pach|Thiele|Tóth|1998}}; {{harvnb|Dujmović|Morin|Wood|2005}}; {{harvnb|Di Giacomo|Liotta|Meijer|2005}}</ref>

In much higher dimensions, sets of grid points with no three in line, obtained by choosing points near a [[hypersphere]], have been used for finding large [[Salem–Spencer set]]s, sets of integers with no three forming an arithmetic progression.{{sfn|Elkin|2011}} 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. The largest convex polygons with vertices in an <math>n\times n</math> grid have only <math>O(n^{2/3})</math> vertices.{{sfn|Jarník|1926}} The [[cap set]] problem concerns a similar problem to the no-three-in-line problem in spaces that are both high-dimensional, and based as [[vector space]]s over [[finite field]]s rather than over the integers.{{sfn|Klarreich|2016}}

Another generalization to higher dimensions is to find as many points as possible in a three dimensional <math>N \times N \times N</math> grid such that no four of them are in the same plane. This sequence begins 5, 8, 10, 13, 16, ... {{oeis|A280537}} for {{math|N {{=}} 2, 3, 4}}, etc.

===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 <math>m\times n</math> grid, the maximum number of points that can be chosen with no three in line is at most {{nowrap|<math>2\gcd(m,n)</math>.{{sfn|Misiak|Stępień|Szymaszkiewicz|Szymaszkiewicz|2016}}}} 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.{{sfn|Cooper|Solymosi|2005}} Higher-dimensional torus versions of the problem have also been studied.{{sfn|Ku|Wong|2018}}

==See also==
*[[Eight queens puzzle]], on placing points on a grid with no two on the same row, column, or diagonal

==Notes==
{{Reflist|30em}}

==References==
{{refbegin|30em}}
*{{cite conference
 | last1 = Adena | first1 = Michael A.
 | last2 = Holton | first2 = Derek A.
 | last3 = Kelly | first3 = Patrick A.
 | editor-last = Holton | editor-first = Derek A.
 | contribution = Some thoughts on the no-three-in-line problem
 | doi = 10.1007/BFb0057371
 | mr = 0349396
 | pages = 6–17
 | series = Lecture Notes in Mathematics
 | title = Combinatorial Mathematics: Proceedings of the Second Australian Conference (University of Melbourne, 1973)
 | volume = 403
 | year = 1974| isbn = 978-3-540-06903-4
 }}
*{{cite journal
 | last1 = Aichholzer | first1 = Oswin
 | last2 = Eppstein | first2 = David | author2-link = David Eppstein
 | last3 = Hainzl | first3 = Eva-Maria
 | title = Geometric dominating sets – a minimum version of the No-Three-In-Line Problem
 | date = January 2023
 | publisher = Elsevier
 | volume = 108
 | journal = Computational Geometry
 | page = 101913
 | doi = 10.1016/j.comgeo.2022.101913| s2cid = 249687906
 | doi-access = free
 | arxiv = 2203.13170
 }}
*{{cite journal
 | last = Anderson | first = David Brent
 | doi = 10.1016/0097-3165(79)90025-6
 | issue = 3
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 555806
 | pages = 365–366
 | series = Series A
 | title = Update on the no-three-in-line problem
 | volume = 27
 | year = 1979| doi-access = free
 }}
*{{cite journal
 | last1 = Brass | first1 = Peter
 | last2 = Cenek | first2 = Eowyn
 | last3 = Duncan | first3 = Christian A.
 | last4 = Efrat | first4 = Alon
 | last5 = Erten | first5 = Cesim
 | last6 = Ismailescu | first6 = Dan P.
 | last7 = Kobourov | first7 = Stephen G.
 | last8 = Lubiw | first8 = Anna | author8-link = Anna Lubiw
 | last9 = Mitchell | first9 = Joseph S. B. | author9-link = Joseph S. B. Mitchell
 | doi = 10.1016/j.comgeo.2006.05.006
 | issue = 2
 | journal = [[Computational Geometry (journal)|Computational Geometry]]
 | mr = 2278011
 | pages = 117–130
 | title = On simultaneous planar graph embeddings
 | volume = 36
 | year = 2007| doi-access = free
 }}
*{{cite book
 | last1 = Brass | first1 = Peter
 | last2 = Moser | first2 = William
 | last3 = Pach | first3 = János | author3-link = János Pach
 | contribution = Section 10.1: Packing lattice points in subspaces
 | contribution-url = https://books.google.com/books?id=cT7TB20y3A8C&pg=PA417
 | isbn = 978-0-387-29929-7
 | mr = 2163782
 | pages = 417–421
 | publisher = Springer, New York
 | title = Research Problems in Discrete Geometry
 | year = 2005}}
*{{cite journal
 | last1 = Cooper | first1 = Alec S.
 | last2 = Pikhurko | first2 = Oleg
 | last3 = Schmitt | first3 = John R.
 | last4 = Warrington | first4 = Gregory S.
 | doi = 10.4169/amer.math.monthly.121.03.213
 | issue = 3
 | journal = [[American Mathematical Monthly]]
 | jstor = 10.4169/amer.math.monthly.121.03.213 
 | pages = 213–221
 | title = Martin Gardner's minimum no-3-in-a-line problem
 | volume = 121
 | year = 2014| arxiv = 1206.5350
 | s2cid = 887220
 }}
*{{cite journal
 | last1 = Cooper | first1 = Joshua N.
 | last2 = Solymosi | first2 = József | author2-link = József Solymosi
 | doi = 10.1007/s00026-005-0248-4
 | issue = 2
 | journal = [[Annals of Combinatorics]]
 | mr = 2153735
 | pages = 169–175
 | title = Collinear points in permutations
 | url = https://people.math.sc.edu/cooper/collinearpre.pdf
 | volume = 9
 | year = 2005| arxiv = math/0408396
 | s2cid = 11035679
 }}
*{{cite journal
 | last1 = Craggs | first1 = D.
 | last2 = Hughes-Jones | first2 = R.
 | doi = 10.1016/0097-3165(76)90030-3 | doi-access = free
 | issue = 3
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 406804
 | pages = 363–364
 | series = Series A
 | title = On the no-three-in-line problem
 | volume = 20
 | year = 1976}}
*{{cite book
 | last = Dudeney | first = Henry | author-link = Henry Dudeney
 | contribution = 317. A puzzle with pawns
 | contribution-url = https://archive.org/stream/amusementsinmath00dude#page/94/mode/2up
 | location = Edinburgh
 | page = 94
 | publisher = Nelson
 | title = Amusements in Mathematics
 | year = 1917}} Solution, [https://archive.org/stream/amusementsinmath00dude#page/222/mode/2up p.&nbsp;222]. Originally published in the London ''Tribune'', November 7, 1906.
*{{cite journal
 | last1 = Di Giacomo | first1 = Emilio
 | last2 = Liotta | first2 = Giuseppe
 | last3 = Meijer | first3 = Henk
 | doi = 10.1016/j.comgeo.2004.11.003 | doi-access = 
 | issue = 1
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
 | pages = 26–58
 | title = Computing straight-line 3d grid drawings of graphs in linear volume
 | volume = 32
 | year = 2005}}
* {{cite journal | last1 = Dujmović
  | first1 = Vida | author1-link = Vida Dujmović
  | last2 = Morin
  | first2 = Pat | author2-link = Pat Morin
  | last3 = Wood
  | first3 = David R. | author3-link = David Wood (mathematician)
  | title = Layout of graphs with bounded tree-width
  | year = 2005
  | journal = [[SIAM Journal on Computing]]
  | volume = 34
  | issue = 3
  | pages = 553–579
  | doi = 10.1137/S0097539702416141| arxiv = cs/0406024
  | s2cid = 3264071
 }}
*{{cite journal
 | last = Elkin | first = Michael
 | arxiv = 0801.4310
 | doi = 10.1007/s11856-011-0061-1 | doi-access = free
 | journal = [[Israel Journal of Mathematics]]
 | mr = 2823971
 | pages = 93–128
 | title = An improved construction of progression-free sets
 | volume = 184
 | year = 2011}}
*{{cite book
 | last = Eppstein | first = David | author-link = David Eppstein
 | publisher = Cambridge University Press
 | contribution = Chapter 9: General position
 | pages = 72–86
 | title = Forbidden Configurations in Discrete Geometry
 | year = 2018}}
* {{cite journal
  | last = Flammenkamp
  | first = Achim
  | title = Progress in the no-three-in-line problem
  | journal = [[Journal of Combinatorial Theory]] | series = Series A
  | volume = 60
  | year = 1992
  | issue = 2
  | pages = 305–311
  | doi = 10.1016/0097-3165(92)90012-J| doi-access = free
  }}
* {{cite journal
  | last = Flammenkamp
  | first = Achim
  | title = Progress in the no-three-in-line problem, II
  | journal = [[Journal of Combinatorial Theory]] | series = Series A
  | volume = 81
  | year = 1998
  | issue = 1
  | pages = 108–113
  | doi = 10.1006/jcta.1997.2829| doi-access = free
  }}
*{{cite journal
 | last1 = Froese | first1 = Vincent
 | last2 = Kanj | first2 = Iyad
 | last3 = Nichterlein | first3 = André
 | last4 = Niedermeier | first4 = Rolf | author4-link=Rolf Niedermeier
 | doi = 10.1142/S021819591750008X
 | issue = 4
 | journal = International Journal of Computational Geometry & Applications
 | mr = 3766097
 | pages = 277–296
 | title = Finding points in general position
 | volume = 27
 | year = 2017| arxiv = 1508.01097
 | s2cid = 47260245
 }}
*{{cite magazine
 | last = Gardner | first = Martin | author-link = Martin Gardner
 | date = October 1976
 | department = Mathematical Games
 | issue = 4
 | magazine = [[Scientific American]]
 | jstor = 24950467
 | pages = 131–137
 | title = Combinatorial problems, some old, some new and all newly attacked by computer
 | volume = 235}}
*{{cite journal
 | last1 = Guy | first1 = R. K. | author1-link = Richard K. Guy
 | last2 = Kelly | first2 = P. A.
 | doi = 10.4153/CMB-1968-062-3 | doi-access = free
 | issue = 4
 | journal = [[Canadian Mathematical Bulletin]]
 | mr = 0238765
 | pages = 527–531
 | title = The no-three-in-line problem
 | volume = 11
 | year = 1968}}
* {{cite journal
  | last1 = Hall    | first1 = R. R.
  | last2 = Jackson | first2 = T. H.
  | last3 = Sudbery | first3 = A.
  | last4 = Wild    | first4 = K.
  | title = Some advances in the no-three-in-line problem
  | journal = [[Journal of Combinatorial Theory]] | series = Series A
  | volume = 18
  | year = 1975
  | issue = 3
  | pages = 336–341
  | doi = 10.1016/0097-3165(75)90043-6| doi-access = free
  }}
*{{cite journal
 | last1 = Harborth | first1 = Heiko | author1-link = Heiko Harborth
 | last2 = Oertel | first2 = Philipp
 | last3 = Prellberg | first3 = Thomas
 | department = Proceedings of the Oberwolfach Meeting “Kombinatorik” (1986)
 | doi = 10.1016/0012-365X(88)90135-5
 | issue = 1–2
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | mr = 974815
 | pages = 89–90
 | title = No-three-in-line for seventeen and nineteen
 | volume = 73
 | year = 1989| doi-access = free
 }}
*{{cite journal
 | last = Jarník | first = Vojtěch
 | doi = 10.1007/BF01216795
 | issue = 1
 | journal = [[Mathematische Zeitschrift]]
 | language = de
 | mr = 1544776
 | pages = 500–518
 | title = Über die Gitterpunkte auf konvexen Kurven
 | trans-title = On the grid points on convex curves
 | url = https://eudml.org/doc/174999
 | volume = 24
 | year = 1926| s2cid = 117747514
 }}
*{{cite magazine|title=Simple Set Game Proof Stuns Mathematicians|magazine=Quanta|first=Erica|last=Klarreich|date=May 31, 2016|url=https://www.quantamagazine.org/20160531-set-proof-stuns-mathematicians/}}
*{{cite journal
 | last = Kløve | first = Torleiv
 | doi = 10.1016/0097-3165(78)90053-5
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 462998
 | pages = 126–127
 | series = Series A
 | title = On the no-three-in-line problem. II
 | volume = 24
 | year = 1978| doi-access = free
 }}
*{{cite journal
 | last = Kløve | first = Torleiv
 | doi = 10.1016/0097-3165(79)90055-4
 | issue = 1
 | journal = [[Journal of Combinatorial Theory]]
 | mr = 525088
 | pages = 82–83
 | series = Series A
 | title = On the no-three-in-line problem. III
 | volume = 26
 | year = 1979| doi-access = 
 }}
*{{cite journal
 | last1 = Komlós | first1 = J. | author1-link = János Komlós (mathematician)
 | last2 = Pintz | first2 = J. | author2-link = János Pintz
 | last3 = Szemerédi | first3 = E. | author3-link = Endre Szemerédi
 | doi = 10.1112/jlms/s2-25.1.13
 | issue = 1
 | journal = [[Journal of the London Mathematical Society]]
 | mr = 0645860
 | pages = 13–24
 | title = A lower bound for Heilbronn's problem
 | volume = 25
 | year = 1982}}
*{{cite book
 | last = Knuth | first = Donald E. | author-link = Donald Knuth
 | contribution = Answer to exercise 242
 | contribution-url = https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz
 | page = 130
 | title = The Art of Computer Programming, Fascicle 1b: A Draft of Section 7.1.4: Binary Decision Diagrams
 | year = 2008}}
*{{cite journal
 | last1 = Ku | first1 = Cheng Yeaw
 | last2 = Wong | first2 = Kok Bin
 | doi = 10.1007/s00373-018-1878-8
 | issue = 2
 | journal = Graphs and Combinatorics
 | mr = 3774457
 | pages = 355–364
 | title = On no-three-in-line problem on {{mvar|m}}-dimensional torus
 | volume = 34
 | year = 2018| s2cid = 3935268
 }}
*{{cite journal
 | last1 = Misiak | first1 = Aleksander
 | last2 = Stępień | first2 = Zofia
 | last3 = Szymaszkiewicz | first3 = Alicja
 | last4 = Szymaszkiewicz | first4 = Lucjan
 | last5 = Zwierzchowski | first5 = Maciej
 | doi = 10.1016/j.disc.2015.08.006
 | issue = 1
 | journal = Discrete Mathematics
 | mr = 3404483
 | pages = 217–221
 | title = A note on the no-three-in-line problem on a torus
 | volume = 339
 | year = 2016| arxiv = 1406.6713
 | s2cid = 40210322
 }}
* {{cite conference
  | first1 = János   | last1 = Pach    | author1-link = János Pach
  | first2 = Torsten | last2 = Thiele
  | first3 = Géza    | last3 = Tóth
  | title = Three-dimensional grid drawings of graphs
  | date = 1998
  | book-title = [[International Symposium on Graph Drawing|Graph Drawing, 5th Int. Symp., GD '97]]
  | series = Lecture Notes in Computer Science | volume= 1353 | publisher= Springer-Verlag
  | pages = 47–51
  |doi =10.1007/3-540-63938-1_49| doi-access = free
  }}
*{{cite journal
 | last1 = Payne | first1 = Michael S.
 | last2 = Wood | first2 = David R. | author2-link = David Wood (mathematician)
 | arxiv = 1208.5289
 | doi = 10.1137/120897493
 | issue = 4
 | journal = SIAM Journal on Discrete Mathematics
 | mr = 3111653
 | pages = 1727–1733
 | title = On the general position subset selection problem
 | volume = 27
 | year = 2013| s2cid = 7164626
 }}
* {{cite web
  | last1 = Pegg | first1 = Ed Jr. | author-link = Ed Pegg Jr.
  | work = Math Games | title = Chessboard Tasks
  | publisher = Mathematical Association of America
  | url=http://www.mathpuzzle.com/MAA/36-Chessboard%20Tasks/mathgames_04_11_05.html
  | date=April 11, 2005
  | access-date=June 25, 2012}}
* {{cite journal
  | first1 = Attila   | last1 = Pór 
  | first2 = David R. | last2 = Wood | author2-link = David Wood (mathematician)
  | title = No-three-in-line-in-3D
  | journal = [[Algorithmica]]
  | year = 2007	
  | doi = 10.1007/s00453-006-0158-9
  | volume = 47
  | issue = 4
  | pages = 481| s2cid = 209841346 }}
* {{ cite journal | last = Roth | first = K. F. | author-link = Klaus Roth
  | title = On a problem of Heilbronn
  | journal = [[Journal of the London Mathematical Society]]
  | volume = 26
  | year = 1951
  | issue = 3
  | pages = 198–204
  | doi = 10.1112/jlms/s1-26.3.198}}
*{{cite journal
 | last = Wood | first = David R. | author-link = David Wood (mathematician)
 | doi = 10.1016/j.comgeo.2004.06.001 | doi-access = free
 | issue = 1
 | journal = [[Computational Geometry (journal)|Computational Geometry: Theory and Applications]]
 | pages = 25–28
 | title = Grid drawings of {{mvar|k}}-colourable graphs
 | volume = 30
 | year = 2005}}
{{refend}}

==External links==
* {{cite web | author = Flammenkamp, Achim | url = http://wwwhomes.uni-bielefeld.de/achim/no3in/readme.html | title = The No-Three-in-Line Problem}}
* {{mathworld | title = No-Three-in-a-Line-Problem | urlname = No-Three-in-a-Line-Problem}}

[[Category:Combinatorics]]
[[Category:Lattice points]]
[[Category:Conjectures]]
[[Category:Mathematical problems]]