2055:, 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. 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
765:
22:
419:
412:
405:
398:
391:
384:
377:
370:
363:
356:
349:
342:
335:
328:
321:
314:
308:
3015:. 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.
3026:, sets of integers with no three forming an arithmetic progression. 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
3173:
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
2302:
This application was the motivation for Paul Erdős to find his solution for the no-three-in-line problem. 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
2190:
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
2059:, 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
2324:. 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
2254:
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
3241:
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. Higher-dimensional torus versions of the problem have also been studied.
1958:
3174:
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
2022:
1960:
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
2733:
that tries to solve the no-three-in-line problem by placing points one at a time until it gets stuck. If only axis-parallel and diagonal lines are considered, then every such set has at least
2407:, 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
1748:
2647:
2594:
2250:
3141:
2868:
2964:
2801:
2298:
1043:
970:
220:
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
2906:
2394:
2209:
1232:
812:
3237:
3094:
3198:
3050:
2723:
1459:
1306:
1280:
550:
61:
4613:
Misiak, Aleksander; Stępień, Zofia; Szymaszkiewicz, Alicja; Szymaszkiewicz, Lucjan; Zwierzchowski, Maciej (2016). "A note on the no-three-in-line problem on a torus".
2651:
The example of the grid shows that this bound cannot be significantly improved. The proof of existence of these large general-position subsets can be converted into a
1834:
1537:
1174:
898:
1433:
1004:
1569:
859:
249:
124:
2757:
2160:
1700:
1650:
1598:
1494:
645:
468:
2987:
2824:
2544:
2130:
1981:
1898:
1865:
1780:
1197:
1080:
921:
786:
686:
597:
524:
274:
218:
193:
151:
95:
3009:
2675:
2524:
2495:
2471:
2449:
2427:
2356:
2188:
2105:
2081:
1802:
1672:
1620:
1396:
1374:
1348:
1326:
1254:
1137:
1113:
832:
753:
729:
617:
570:
499:
171:
2191:
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
1875:
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
1060:
4799:
4527:
280:
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
3145:
698:
659:
472:
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
429:
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.
4665:
1905:
1986:
3827:
3654:
Adena, Michael A.; Holton, Derek A.; Kelly, Patrick A. (1974). "Some thoughts on the no-three-in-line problem". In Holton, Derek A. (ed.).
2759:
points. However, less is known about the version of the problem where all lines are considered: every greedy placement includes at least
71:
in 1900. Brass, Moser, and Pach call it "one of the oldest and most extensively studied geometric questions concerning lattice points".
4514:
3845:
Cooper, Alec S.; Pikhurko, Oleg; Schmitt, John R.; Warrington, Gregory S. (2014). "Martin
Gardner's minimum no-3-in-a-line problem".
4016:
Di
Giacomo, Emilio; Liotta, Giuseppe; Meijer, Henk (2005). "Computing straight-line 3d grid drawings of graphs in linear volume".
4833:
4018:
3779:
4485:
4452:
4327:
4185:
4156:
3960:
3734:
4916:
4359:
4290:
2403:
One can get a finer-grained understanding of the running time of algorithms for finding the exact optimal solution by using
4097:
3847:
3100:
problem concerns a similar problem to the no-three-in-line problem in spaces that are both high-dimensional, and based as
3170:
2332:
its size to within a constant factor; this hardness of approximation result is summarized by saying that the problem is
3765:
Brass, Peter; Cenek, Eowyn; Duncan, Christian A.; Efrat, Alon; Erten, Cesim; Ismailescu, Dan P.; Kobourov, Stephen G.;
4262:(October 1976). "Combinatorial problems, some old, some new and all newly attacked by computer". Mathematical Games.
4820:
4760:
4685:
4047:
2167:
473:
289:
4396:
4052:
2500:
2400:
that simply chooses points one at a time until all remaining points lie on lines through pairs of chosen points.
2404:
2032:
281:
4739:
4906:
3907:
2329:
2063:, but other graphs that can be colored with fewer colors can also be drawn on smaller grids: if a graph has
1706:
733:
is not known. However, both proven and conjectured bounds limit this number to within a range proportional
4901:
4434:
3656:
Combinatorial
Mathematics: Proceedings of the Second Australian Conference (University of Melbourne, 1973)
2317:
3111:
Another generalization to higher dimensions is to find as many points as possible in a three dimensional
3023:
3018:
In much higher dimensions, sets of grid points with no three in line, obtained by choosing points near a
3770:
2603:
2550:
2220:
2040:
3114:
2841:
4005:
2914:
2762:
2259:
4911:
3995:
1807:
1009:
928:
442:
onto the board so that no three are in a line. This is exactly the no-three-in-line problem, for the
127:
3878:
2875:
2366:
4264:
3251:
2680:
2361:
2044:
2194:
1205:
4782:
4723:
4697:
4648:
4622:
4601:
4421:
4269:
4247:
4221:
4106:
4079:
4061:
3942:
3916:
3882:
3874:
3856:
3716:
3696:
3143:
grid such that no four of them are in the same plane. This sequence begins 5, 8, 10, 13, 16, ...
791:
4877:
4565:
The Art of
Computer Programming, Fascicle 1b: A Draft of Section 7.1.4: Binary Decision Diagrams
4522:
3895:
3204:
3055:
2166:
The no-three-in-line problem also has applications to another problem in discrete geometry, the
764:
438:
in 1900, as a puzzle in recreational mathematics, phrased in terms of placing the 16 pawns of a
3177:
3029:
2702:
1438:
1285:
1259:
529:
40:
4874:
3823:
3815:
2212:
1813:
1499:
1143:
867:
34:
4842:
4808:
4774:
4707:
4670:
4632:
4585:
4536:
4494:
4461:
4405:
4368:
4336:
4299:
4231:
4209:
4194:
4165:
4116:
4071:
4039:
4027:
3969:
3926:
3866:
3788:
3743:
3706:
3659:
2730:
2397:
2321:
1403:
4865:
4719:
4644:
4597:
4548:
4506:
4475:
4417:
4382:
4313:
4243:
4130:
3983:
3938:
3837:
3802:
3757:
3671:
977:
4715:
4640:
4593:
4560:
4544:
4502:
4471:
4413:
4378:
4309:
4239:
4126:
3979:
3934:
3833:
3798:
3753:
3667:
2652:
1545:
838:
223:
100:
3870:
2736:
2139:
1677:
1627:
1575:
1471:
624:
447:
2969:
2806:
2729:
has three in a line. Equivalently, this is the smallest set that could be produced by a
2112:
1963:
1880:
1847:
1762:
1179:
1065:
903:
771:
668:
579:
506:
256:
200:
178:
133:
77:
4518:
4350:
4281:
4259:
4138:
3680:
3200:
grid, the maximum number of points that can be chosen with no three in line is at most
2994:
2696:
2660:
2529:
2509:
2480:
2456:
2434:
2412:
2341:
2173:
2090:
2084:
2066:
2060:
2056:
1787:
1657:
1605:
1381:
1359:
1333:
1311:
1239:
1122:
1098:
817:
738:
714:
602:
555:
484:
156:
4669:. Lecture Notes in Computer Science. Vol. 1353. Springer-Verlag. pp. 47–51.
1049:
4895:
4786:
4660:
4498:
4466:
4447:
4425:
4373:
4354:
4341:
4322:
4170:
4151:
3991:
3974:
3955:
3899:
3811:
3748:
3729:
3720:
2052:
2036:
1088:
435:
285:
68:
63:
grid so that no three points lie on the same line. The problem concerns lines of all
4652:
4251:
3946:
4765:
4727:
4663:; Thiele, Torsten; Tóth, Géza (1998). "Three-dimensional grid drawings of graphs".
4605:
4556:
4083:
3105:
3101:
2048:
1116:
3886:
2134:
The no-three-in-line drawing of a complete graph is a special case of this result
4847:
4824:
4031:
3793:
3774:
3711:
3684:
2725:
grid that cannot be extended: it has no three points in a line, but every proper
4735:
3019:
2031:
Solutions to the no-three-in-line problem can be used to avoid certain kinds of
1872:
4812:
4636:
3685:"Geometric dominating sets – a minimum version of the No-Three-In-Line Problem"
2910:
Similarly to Erdős's 2D construction, this can be accomplished by using points
21:
4794:
4778:
4589:
4540:
4235:
4121:
4092:
4075:
3930:
3766:
3254:, on placing points on a grid with no two on the same row, column, or diagonal
3165:
Another variation on the problem involves converting the grid into a discrete
2834:
Non-collinear sets of points in the three-dimensional grid were considered by
2679:
of size matching the existence bound, using an algorithmic technique known as
1810:
some three of them would all lie on the same horizontal line of the grid. For
652:
1, 2, 11, 32, 50, 132, 380, 368, 1135, 1120, 4348, 3622, 10568, ... (sequence
439:
4675:
4882:
4043:
1540:
1353:
4304:
4285:
4199:
4180:
3613:
2726:
2333:
4273:
2431:
it can be found in an amount of time that is an exponential function of
4409:
3663:
3097:
2325:
479:
Many authors have published solutions to this problem for small values
4711:
4572:
Ku, Cheng Yeaw; Wong, Kok Bin (2018). "On no-three-in-line problem on
2043:
of a given graph at integer coordinates in the plane, and drawing the
3921:
126:
points in a grid would include a row of three or more points, by the
25:
A set of 20 points in a 10 × 10 grid, with no three points in a line.
3423:. The discovery of this error was credited by Pegg to Gabor Ellmann.
691:
1, 1, 4, 5, 11, 22, 57, 51, 156, 158, 566, 499, 1366, ... (sequence
4226:
4066:
3701:
1871:
conjectured that for large grids, there is a significantly smaller
4702:
4627:
4214:
International
Journal of Computational Geometry & Applications
4111:
3861:
3166:
763:
64:
20:
2803:
points before getting stuck, but nothing better than the trivial
2598:
there exist general-position subsets of size nearly proportional
4357:. Proceedings of the Oberwolfach Meeting “Kombinatorik” (1986).
3495:
2320:, finite sets of points with no three in line are said to be in
4483:
Kløve, Torleiv (1979). "On the no-three-in-line problem. III".
4391:
3522:
3658:. Lecture Notes in Mathematics. Vol. 403. pp. 6–17.
1953:{\displaystyle c={\sqrt{\frac {2\pi ^{2}}{3}}}\approx 1.874.}
709:
The exact number of points that can be placed, as a function
67:, not only those aligned with the grid. It was introduced by
4688:(2013). "On the general position subset selection problem".
4321:
Hall, R. R.; Jackson, T. H.; Sudbery, A.; Wild, K. (1975).
3149:
693:
654:
2328:
to find this subset, for certain input sets, and hard to
2211:
within the unit square, with no three in a line, then by
2107:
colors, it can be drawn in a grid with area proportional
2017:{\displaystyle c={\frac {\pi }{\sqrt {3}}}\approx 1.814.}
3534:
3479:
3477:
3345:
2838:. They proved that the maximum number of points in the
1052:
3566:
3395:
3382:
Erdős did not publish this observation; it appears in
2606:
2553:
2532:
1711:
1465:
1256:
is not prime, one can perform this construction for a
576:
and some larger values. The numbers of solutions with
3432:
3301:
3299:
3297:
3295:
3207:
3180:
3117:
3058:
3032:
2997:
2972:
2917:
2878:
2844:
2809:
2765:
2739:
2705:
2663:
2512:
2483:
2459:
2437:
2415:
2369:
2344:
2262:
2223:
2197:
2176:
2142:
2115:
2093:
2069:
1989:
1966:
1908:
1883:
1850:
1816:
1790:
1765:
1709:
1680:
1660:
1630:
1608:
1578:
1548:
1502:
1474:
1441:
1406:
1384:
1362:
1336:
1314:
1288:
1262:
1242:
1208:
1182:
1146:
1125:
1101:
1068:
1012:
980:
931:
906:
870:
841:
820:
794:
774:
741:
717:
671:
665:
The numbers of equivalence classes of solutions with
627:
605:
582:
558:
532:
509:
487:
450:
259:
226:
203:
181:
159:
136:
103:
80:
43:
4050:(2005). "Layout of graphs with bounded tree-width".
3468:
1539:
points, by placing points in multiple copies of the
4093:"An improved construction of progression-free sets"
3816:"Section 10.1: Packing lattice points in subspaces"
1674:one can perform this construction for a prime near
1622:may be chosen arbitrarily as long as it is nonzero
814:grid, using the method of Erdős. The largest prime
476:, attacking each other in the center of the board.
284:, the no-three-in-line problem has applications in
3329:
3231:
3192:
3135:
3088:
3044:
3003:
2981:
2958:
2900:
2862:
2818:
2795:
2751:
2717:
2669:
2641:
2588:
2538:
2518:
2489:
2475:with the exponent of the polynomial not depending
2465:
2443:
2421:
2388:
2350:
2292:
2244:
2203:
2182:
2154:
2124:
2099:
2075:
2016:
1975:
1952:
1892:
1859:
1828:
1796:
1774:
1742:
1694:
1666:
1644:
1614:
1592:
1563:
1531:
1488:
1453:
1427:
1390:
1368:
1342:
1320:
1300:
1274:
1248:
1226:
1191:
1168:
1131:
1107:
1074:
1054:
1037:
998:
964:
915:
892:
853:
826:
806:
780:
747:
723:
680:
639:
611:
591:
564:
544:
518:
493:
462:
268:
243:
212:
187:
165:
145:
118:
89:
55:
4525:(1982). "A lower bound for Heilbronn's problem".
4208:Froese, Vincent; Kanj, Iyad; Nichterlein, André;
3562:
2499:Problems with this kind of time bound are called
2039:. The problem they apply to involves placing the
3211:
2692:
2655:algorithm for finding a general-position subset
301:
4834:Computational Geometry: Theory and Applications
4394:[On the grid points on convex curves].
4323:"Some advances in the no-three-in-line problem"
4268:. Vol. 235, no. 4. pp. 131–137.
4019:Computational Geometry: Theory and Applications
4212:(2017). "Finding points in general position".
4181:"Progress in the no-three-in-line problem, II"
3625:
3558:
3270:
4355:"No-three-in-line for seventeen and nineteen"
4353:; Oertel, Philipp; Prellberg, Thomas (1989).
4145:. Cambridge University Press. pp. 72–86.
4143:Forbidden Configurations in Discrete Geometry
1464:Erdős' bound has been improved subsequently:
8:
4435:"Simple Set Game Proof Stuns Mathematicians"
1806:For, if more points are placed, then by the
1356:is much smaller than the primes themselves,
4392:"Über die Gitterpunkte auf konvexen Kurven"
3370:
3366:
3353:
3349:
1836:, this trivial bound is known to be tight.
688:points under reflections and rotations are
4800:Journal of the London Mathematical Society
4528:Journal of the London Mathematical Society
4152:"Progress in the no-three-in-line problem"
863:the solution places points at coordinates
130:. Although the problem can be solved with
37:asks how many points can be placed in the
4846:
4701:
4674:
4626:
4465:
4372:
4340:
4303:
4225:
4198:
4169:
4120:
4110:
4065:
3973:
3920:
3860:
3792:
3775:"On simultaneous planar graph embeddings"
3747:
3710:
3700:
3601:
3510:
3285:, April 29 and May 13, 1900, as cited by
3206:
3179:
3116:
3073:
3069:
3057:
3031:
2996:
2971:
2950:
2937:
2916:
2889:
2877:
2843:
2808:
2780:
2776:
2764:
2738:
2704:
2662:
2629:
2621:
2619:
2605:
2576:
2568:
2566:
2552:
2531:
2511:
2482:
2458:
2436:
2414:
2376:
2368:
2343:
2281:
2272:
2261:
2234:
2228:
2222:
2196:
2175:
2141:
2114:
2092:
2068:
1996:
1988:
1965:
1937:
1926:
1915:
1907:
1882:
1849:
1815:
1789:
1764:
1710:
1708:
1684:
1679:
1659:
1634:
1629:
1607:
1582:
1577:
1547:
1521:
1501:
1496:is prime, one can obtain a solution with
1478:
1473:
1440:
1405:
1383:
1361:
1335:
1313:
1287:
1261:
1241:
1236:contains no three collinear points. When
1207:
1181:
1160:
1145:
1124:
1100:
1067:
1051:
1017:
1011:
979:
930:
905:
884:
869:
840:
819:
793:
773:
740:
716:
670:
626:
604:
581:
557:
531:
508:
486:
449:
258:
233:
225:
202:
180:
158:
135:
102:
79:
42:
3822:. Springer, New York. pp. 417–421.
3730:"Update on the no-three-in-line problem"
3535:Aichholzer, Eppstein & Hainzl (2023)
3499:
3483:
3407:
3341:
2451:multiplied by a polynomial in the input
1868:
1095:, is based on the observation that when
4141:(2018). "Chapter 9: General position".
3546:
3317:
3305:
3263:
2835:
3820:Research Problems in Discrete Geometry
3637:
3589:
1782:points may be placed in a grid of any
4797:(1951). "On a problem of Heilbronn".
4746:. Mathematical Association of America
4666:Graph Drawing, 5th Int. Symp., GD '97
4448:"On the no-three-in-line problem. II"
4008:. Originally published in the London
3954:Craggs, D.; Hughes-Jones, R. (1976).
3577:
3346:Harborth, Oertel & Prellberg 1989
3337:
3333:
3286:
1867:points can be placed on small grids,
1743:{\displaystyle {\tfrac {3}{2}}n-o(n)}
1461:grid with no three points collinear.
552:grid with no three in a line for all
418:
411:
404:
397:
390:
383:
376:
369:
362:
355:
348:
341:
334:
327:
320:
313:
304:
7:
4690:SIAM Journal on Discrete Mathematics
3879:10.4169/amer.math.monthly.121.03.213
3871:10.4169/amer.math.monthly.121.03.213
3683:; Hainzl, Eva-Maria (January 2023).
3567:Di Giacomo, Liotta & Meijer 2005
3456:
3444:
3420:
3383:
2870:grid with no three points collinear
2699:asked for the smallest subset of an
1400:so this method can be used to place
1092:
3022:, have been used for finding large
2642:{\textstyle \ell =O({\sqrt {|S|}})}
2589:{\textstyle \ell =O({\sqrt {|S|}})}
4763:(2007). "No-three-in-line-in-3D".
3900:"Collinear points in permutations"
3469:Komlós, Pintz & Szemerédi 1982
2879:
2766:
2263:
2245:{\displaystyle \varepsilon ^{2}/2}
2215:every triangle would have area at
2170:. In this problem, one must place
2051:. For certain graphs, such as the
197:it is conjectured that fewer than
14:
4433:Klarreich, Erica (May 31, 2016).
3956:"On the no-three-in-line problem"
3136:{\displaystyle N\times N\times N}
2863:{\displaystyle n\times n\times n}
2360:a solution with the non-constant
4002:. Edinburgh: Nelson. p. 94.
2959:{\displaystyle (x,y,x^{2}+y^{2}}
2796:{\displaystyle \Omega (n^{2/3})}
2693:Adena, Holton & Kelly (1974)
2293:{\displaystyle \Omega (1/n^{2})}
1328:is the largest prime that is at
417:
410:
403:
396:
389:
382:
375:
368:
361:
354:
347:
340:
333:
326:
319:
312:
306:
4486:Journal of Combinatorial Theory
4453:Journal of Combinatorial Theory
4328:Journal of Combinatorial Theory
4186:Journal of Combinatorial Theory
4157:Journal of Combinatorial Theory
3961:Journal of Combinatorial Theory
3735:Journal of Combinatorial Theory
3563:Dujmović, Morin & Wood 2005
3108:rather than over the integers.
1038:{\displaystyle 4^{2}=16\cong 5}
965:{\displaystyle i=0,1,\dots p-1}
434:The problem was first posed by
18:Geometry problem on grid points
4866:"The No-Three-in-Line Problem"
4291:Canadian Mathematical Bulletin
4286:"The no-three-in-line problem"
3810:Brass, Peter; Moser, William;
3728:Anderson, David Brent (1979).
3330:Craggs & Hughes-Jones 1976
3226:
3214:
3083:
3062:
2976:
2918:
2901:{\displaystyle \Theta (n^{2})}
2895:
2882:
2790:
2769:
2636:
2630:
2622:
2616:
2583:
2577:
2569:
2563:
2389:{\displaystyle O({\sqrt {k}})}
2383:
2373:
2307:Generalizations and variations
2287:
2266:
1737:
1731:
1518:
1506:
1422:
1416:
1354:gap between consecutive primes
1186:
1147:
993:
981:
910:
871:
503:and by 1998 it was known that
97:points can be placed, because
1:
4098:Israel Journal of Mathematics
3848:American Mathematical Monthly
526:points could be placed on an
4878:"No-Three-in-a-Line-Problem"
4848:10.1016/j.comgeo.2004.06.001
4499:10.1016/0097-3165(79)90055-4
4467:10.1016/0097-3165(78)90053-5
4374:10.1016/0012-365X(88)90135-5
4342:10.1016/0097-3165(75)90043-6
4171:10.1016/0097-3165(92)90012-J
4032:10.1016/j.comgeo.2004.11.003
3975:10.1016/0097-3165(76)90030-3
3794:10.1016/j.comgeo.2006.05.006
3749:10.1016/0097-3165(79)90025-6
3712:10.1016/j.comgeo.2022.101913
3559:Pach, Thiele & Tóth 1998
3271:Brass, Moser & Pach 2005
3171:periodic boundary conditions
2336:. If the largest subset has
2204:{\displaystyle \varepsilon }
1227:{\displaystyle 0\leq i<n}
4179:Flammenkamp, Achim (1998).
4150:Flammenkamp, Achim (1992).
834:less than the grid size is
807:{\displaystyle 12\times 12}
599:points for small values of
4933:
4637:10.1016/j.disc.2015.08.006
3996:"317. A puzzle with pawns"
3626:Cooper & Solymosi 2005
3232:{\displaystyle 2\gcd(m,n)}
3089:{\displaystyle O(n^{2/3})}
2691:Repeating a suggestion of
2303:no-three-in-line problem.
2168:Heilbronn triangle problem
1702:to obtain a solution with
290:Heilbronn triangle problem
4779:10.1007/s00453-006-0158-9
4590:10.1007/s00373-018-1878-8
4397:Mathematische Zeitschrift
4236:10.1142/S021819591750008X
4122:10.1007/s11856-011-0061-1
4076:10.1137/S0097539702416141
4053:SIAM Journal on Computing
4000:Amusements in Mathematics
3931:10.1007/s00026-005-0248-4
3193:{\displaystyle m\times n}
3045:{\displaystyle n\times n}
2718:{\displaystyle n\times n}
2501:fixed-parameter tractable
2047:of the graph as straight
1454:{\displaystyle n\times n}
1301:{\displaystyle n\times n}
1275:{\displaystyle p\times p}
760:General placement methods
545:{\displaystyle n\times n}
56:{\displaystyle n\times n}
4813:10.1112/jlms/s1-26.3.198
4676:10.1007/3-540-63938-1_49
4578:Graphs and Combinatorics
4561:"Answer to exercise 242"
4390:Jarník, Vojtěch (1926).
3011:is a prime congruent to
2405:parameterized complexity
2312:General-position subsets
1829:{\displaystyle n\leq 46}
1532:{\displaystyle 3(n-2)/2}
1169:{\displaystyle (i,i^{2}}
893:{\displaystyle (i,i^{2}}
768:Suboptimal placement of
282:recreational mathematics
31:no-three-in-line problem
4541:10.1112/jlms/s2-25.1.13
4446:Kløve, Torleiv (1978).
4284:; Kelly, P. A. (1968).
4091:Elkin, Michael (2011).
3908:Annals of Combinatorics
4305:10.4153/CMB-1968-062-3
4200:10.1006/jcta.1997.2829
3780:Computational Geometry
3771:Mitchell, Joseph S. B.
3689:Computational Geometry
3233:
3194:
3137:
3090:
3046:
3005:
2983:
2960:
2902:
2864:
2826:upper bound is known.
2820:
2797:
2753:
2719:
2671:
2643:
2590:
2546:points per line, with
2540:
2520:
2491:
2467:
2445:
2423:
2390:
2352:
2318:computational geometry
2294:
2246:
2205:
2184:
2156:
2126:
2101:
2077:
2018:
1977:
1954:
1894:
1869:Guy & Kelly (1968)
1861:
1830:
1798:
1776:
1744:
1696:
1668:
1646:
1616:
1594:
1565:
1533:
1490:
1455:
1429:
1428:{\displaystyle n-o(n)}
1392:
1370:
1344:
1322:
1302:
1282:grid contained in the
1276:
1250:
1228:
1193:
1170:
1133:
1109:
1084:
1076:
1056:
1039:
1000:
966:
917:
894:
855:
828:
808:
782:
749:
725:
705:Upper and lower bounds
682:
641:
613:
593:
566:
546:
520:
495:
464:
270:
245:
214:
189:
167:
147:
120:
91:
57:
26:
4917:Mathematical problems
4576:-dimensional torus".
3511:Payne & Wood 2013
3234:
3195:
3138:
3091:
3047:
3006:
2984:
2961:
2903:
2865:
2836:Pór & Wood (2007)
2821:
2798:
2754:
2720:
2672:
2644:
2591:
2541:
2521:
2492:
2468:
2446:
2424:
2396:can be obtained by a
2391:
2353:
2295:
2247:
2206:
2185:
2157:
2127:
2102:
2078:
2019:
1978:
1955:
1895:
1862:
1831:
1799:
1777:
1745:
1697:
1669:
1654:Again, for arbitrary
1647:
1617:
1595:
1566:
1534:
1491:
1456:
1430:
1393:
1376:will always be close
1371:
1345:
1323:
1303:
1277:
1251:
1229:
1194:
1171:
1134:
1110:
1077:
1057:
1040:
1001:
999:{\displaystyle (4,5)}
967:
918:
895:
856:
829:
809:
783:
767:
750:
726:
683:
642:
614:
594:
567:
547:
521:
496:
465:
271:
246:
215:
190:
168:
148:
121:
92:
58:
24:
4864:Flammenkamp, Achim.
4615:Discrete Mathematics
4360:Discrete Mathematics
3695:. Elsevier: 101913.
3408:Guy & Kelly 1968
3205:
3178:
3115:
3056:
3030:
2995:
2970:
2915:
2876:
2842:
2807:
2763:
2737:
2703:
2661:
2604:
2551:
2530:
2510:
2481:
2457:
2435:
2413:
2367:
2342:
2260:
2221:
2195:
2174:
2140:
2113:
2091:
2067:
1987:
1964:
1906:
1881:
1848:
1814:
1808:pigeonhole principle
1788:
1763:
1707:
1678:
1658:
1628:
1606:
1576:
1564:{\displaystyle xy=k}
1546:
1500:
1472:
1439:
1404:
1382:
1360:
1334:
1312:
1286:
1260:
1240:
1206:
1180:
1144:
1123:
1099:
1066:
1050:
1010:
1006:is included because
978:
929:
904:
868:
854:{\displaystyle p=11}
839:
818:
792:
772:
739:
715:
669:
625:
603:
580:
556:
530:
507:
485:
448:
257:
244:{\displaystyle 3n/2}
224:
201:
179:
157:
134:
128:pigeonhole principle
119:{\displaystyle 2n+1}
101:
78:
41:
4829:-colourable graphs"
4684:Payne, Michael S.;
4265:Scientific American
4012:, November 7, 1906.
3894:Cooper, Joshua N.;
3679:Aichholzer, Oswin;
3547:Pór & Wood 2007
3348:; Flammenkamp
3283:The Weekly Dispatch
3252:Eight queens puzzle
2752:{\displaystyle n-1}
2681:entropy compression
2362:approximation ratio
2155:{\displaystyle k=n}
1695:{\displaystyle n/2}
1645:{\displaystyle n/2}
1593:{\displaystyle n/2}
1489:{\displaystyle n/2}
640:{\displaystyle n=2}
463:{\displaystyle n=8}
4875:Weisstein, Eric W.
4825:"Grid drawings of
4740:"Chessboard Tasks"
4738:(April 11, 2005).
4410:10.1007/BF01216795
3664:10.1007/BFb0057371
3638:Ku & Wong 2018
3614:Misiak et al. 2016
3523:Cooper et al. 2014
3496:Froese et al. 2017
3229:
3190:
3133:
3086:
3042:
3024:Salem–Spencer sets
3001:
2982:{\displaystyle p)}
2979:
2956:
2898:
2860:
2819:{\displaystyle 2n}
2816:
2793:
2749:
2715:
2667:
2639:
2586:
2539:{\textstyle \ell }
2536:
2516:
2487:
2463:
2441:
2419:
2386:
2348:
2290:
2242:
2201:
2180:
2152:
2125:{\displaystyle nk}
2122:
2097:
2073:
2014:
1976:{\displaystyle cn}
1973:
1950:
1893:{\displaystyle cn}
1890:
1860:{\displaystyle 2n}
1857:
1840:Conjectured bounds
1826:
1794:
1775:{\displaystyle 2n}
1772:
1740:
1720:
1692:
1664:
1642:
1612:
1590:
1561:
1529:
1486:
1466:Hall et al. (1975)
1451:
1425:
1388:
1366:
1340:
1318:
1298:
1272:
1246:
1224:
1192:{\displaystyle n)}
1189:
1166:
1129:
1105:
1085:
1075:{\displaystyle 11}
1072:
1035:
996:
962:
916:{\displaystyle p)}
913:
890:
851:
824:
804:
781:{\displaystyle 11}
778:
745:
721:
681:{\displaystyle 2n}
678:
637:
609:
592:{\displaystyle 2n}
589:
562:
542:
519:{\displaystyle 2n}
516:
491:
460:
269:{\displaystyle 2n}
266:
241:
213:{\displaystyle 2n}
210:
188:{\displaystyle 46}
185:
163:
146:{\displaystyle 2n}
143:
116:
90:{\displaystyle 2n}
87:
53:
27:
4712:10.1137/120897493
4210:Niedermeier, Rolf
3829:978-0-387-29929-7
3433:Brass et al. 2007
3365:Flammenkamp
3004:{\displaystyle p}
2830:Higher dimensions
2670:{\displaystyle S}
2634:
2581:
2519:{\displaystyle S}
2490:{\displaystyle k}
2466:{\displaystyle n}
2444:{\displaystyle k}
2422:{\displaystyle k}
2381:
2351:{\displaystyle k}
2183:{\displaystyle n}
2100:{\displaystyle k}
2076:{\displaystyle n}
2006:
2005:
1942:
1936:
1844:Although exactly
1797:{\displaystyle n}
1719:
1667:{\displaystyle n}
1615:{\displaystyle k}
1391:{\displaystyle n}
1369:{\displaystyle p}
1343:{\displaystyle n}
1321:{\displaystyle p}
1249:{\displaystyle n}
1132:{\displaystyle n}
1108:{\displaystyle n}
827:{\displaystyle p}
748:{\displaystyle n}
724:{\displaystyle n}
612:{\displaystyle n}
565:{\displaystyle n}
494:{\displaystyle n}
474:squares d4 and e5
427:
426:
166:{\displaystyle n}
153:points for every
35:discrete geometry
4924:
4888:
4887:
4869:
4852:
4850:
4828:
4816:
4790:
4755:
4753:
4751:
4731:
4705:
4696:(4): 1727–1733.
4680:
4678:
4656:
4630:
4609:
4575:
4568:
4557:Knuth, Donald E.
4552:
4510:
4479:
4469:
4442:
4429:
4386:
4376:
4346:
4344:
4317:
4307:
4277:
4255:
4229:
4204:
4202:
4175:
4173:
4146:
4134:
4124:
4114:
4087:
4069:
4035:
4003:
3987:
3977:
3950:
3924:
3904:
3896:Solymosi, József
3890:
3864:
3841:
3806:
3796:
3761:
3751:
3724:
3714:
3704:
3675:
3641:
3635:
3629:
3623:
3617:
3611:
3605:
3599:
3593:
3587:
3581:
3575:
3569:
3556:
3550:
3544:
3538:
3532:
3526:
3520:
3514:
3508:
3502:
3493:
3487:
3481:
3472:
3466:
3460:
3454:
3448:
3442:
3436:
3430:
3424:
3417:
3411:
3405:
3399:
3396:Hall et al. 1975
3393:
3387:
3380:
3374:
3363:
3357:
3327:
3321:
3315:
3309:
3303:
3290:
3280:
3274:
3268:
3240:
3238:
3236:
3235:
3230:
3199:
3197:
3196:
3191:
3156:
3152:
3142:
3140:
3139:
3134:
3095:
3093:
3092:
3087:
3082:
3081:
3077:
3051:
3049:
3048:
3043:
3014:
3010:
3008:
3007:
3002:
2990:
2988:
2986:
2985:
2980:
2965:
2963:
2962:
2957:
2955:
2954:
2942:
2941:
2909:
2907:
2905:
2904:
2899:
2894:
2893:
2869:
2867:
2866:
2861:
2825:
2823:
2822:
2817:
2802:
2800:
2799:
2794:
2789:
2788:
2784:
2758:
2756:
2755:
2750:
2731:greedy algorithm
2724:
2722:
2721:
2716:
2687:Greedy placement
2678:
2676:
2674:
2673:
2668:
2650:
2648:
2646:
2645:
2640:
2635:
2633:
2625:
2620:
2597:
2595:
2593:
2592:
2587:
2582:
2580:
2572:
2567:
2545:
2543:
2542:
2537:
2525:
2523:
2522:
2517:
2498:
2496:
2494:
2493:
2488:
2474:
2472:
2470:
2469:
2464:
2450:
2448:
2447:
2442:
2430:
2428:
2426:
2425:
2420:
2398:greedy algorithm
2395:
2393:
2392:
2387:
2382:
2377:
2359:
2357:
2355:
2354:
2349:
2322:general position
2301:
2299:
2297:
2296:
2291:
2286:
2285:
2276:
2253:
2251:
2249:
2248:
2243:
2238:
2233:
2232:
2210:
2208:
2207:
2202:
2189:
2187:
2186:
2181:
2163:
2161:
2159:
2158:
2153:
2133:
2131:
2129:
2128:
2123:
2106:
2104:
2103:
2098:
2082:
2080:
2079:
2074:
2023:
2021:
2020:
2015:
2007:
2001:
1997:
1982:
1980:
1979:
1974:
1959:
1957:
1956:
1951:
1943:
1941:
1932:
1931:
1930:
1917:
1916:
1901:
1899:
1897:
1896:
1891:
1866:
1864:
1863:
1858:
1835:
1833:
1832:
1827:
1805:
1803:
1801:
1800:
1795:
1781:
1779:
1778:
1773:
1751:
1749:
1747:
1746:
1741:
1721:
1712:
1701:
1699:
1698:
1693:
1688:
1673:
1671:
1670:
1665:
1653:
1651:
1649:
1648:
1643:
1638:
1621:
1619:
1618:
1613:
1601:
1599:
1597:
1596:
1591:
1586:
1570:
1568:
1567:
1562:
1538:
1536:
1535:
1530:
1525:
1495:
1493:
1492:
1487:
1482:
1468:show that, when
1460:
1458:
1457:
1452:
1434:
1432:
1431:
1426:
1399:
1397:
1395:
1394:
1389:
1375:
1373:
1372:
1367:
1351:
1349:
1347:
1346:
1341:
1327:
1325:
1324:
1319:
1307:
1305:
1304:
1299:
1281:
1279:
1278:
1273:
1255:
1253:
1252:
1247:
1235:
1233:
1231:
1230:
1225:
1200:
1198:
1196:
1195:
1190:
1175:
1173:
1172:
1167:
1165:
1164:
1138:
1136:
1135:
1130:
1114:
1112:
1111:
1106:
1083:
1081:
1079:
1078:
1073:
1061:
1059:
1058:
1055:{\displaystyle }
1053:
1044:
1042:
1041:
1036:
1022:
1021:
1005:
1003:
1002:
997:
973:
971:
969:
968:
963:
923:
922:
920:
919:
914:
899:
897:
896:
891:
889:
888:
862:
860:
858:
857:
852:
833:
831:
830:
825:
813:
811:
810:
805:
787:
785:
784:
779:
756:
754:
752:
751:
746:
732:
730:
728:
727:
722:
696:
687:
685:
684:
679:
657:
648:
646:
644:
643:
638:
618:
616:
615:
610:
598:
596:
595:
590:
575:
571:
569:
568:
563:
551:
549:
548:
543:
525:
523:
522:
517:
502:
500:
498:
497:
492:
471:
469:
467:
466:
461:
421:
420:
414:
413:
407:
406:
400:
399:
393:
392:
386:
385:
379:
378:
372:
371:
365:
364:
358:
357:
351:
350:
344:
343:
337:
336:
330:
329:
323:
322:
316:
315:
310:
309:
302:
277:
275:
273:
272:
267:
250:
248:
247:
242:
237:
219:
217:
216:
211:
196:
194:
192:
191:
186:
172:
170:
169:
164:
152:
150:
149:
144:
125:
123:
122:
117:
96:
94:
93:
88:
62:
60:
59:
54:
4932:
4931:
4927:
4926:
4925:
4923:
4922:
4921:
4892:
4891:
4873:
4872:
4863:
4860:
4855:
4826:
4819:
4793:
4758:
4749:
4747:
4734:
4683:
4659:
4612:
4573:
4571:
4555:
4513:
4482:
4445:
4432:
4389:
4351:Harborth, Heiko
4349:
4320:
4280:
4260:Gardner, Martin
4258:
4207:
4178:
4149:
4139:Eppstein, David
4137:
4090:
4038:
4015:
3990:
3953:
3902:
3893:
3844:
3830:
3809:
3764:
3727:
3681:Eppstein, David
3678:
3653:
3649:
3644:
3636:
3632:
3624:
3620:
3612:
3608:
3600:
3596:
3588:
3584:
3576:
3572:
3557:
3553:
3545:
3541:
3533:
3529:
3521:
3517:
3509:
3505:
3494:
3490:
3482:
3475:
3467:
3463:
3455:
3451:
3443:
3439:
3431:
3427:
3419:As reported by
3418:
3414:
3406:
3402:
3394:
3390:
3381:
3377:
3364:
3360:
3328:
3324:
3316:
3312:
3304:
3293:
3281:
3277:
3269:
3265:
3261:
3248:
3203:
3202:
3201:
3176:
3175:
3163:
3154:
3144:
3113:
3112:
3065:
3054:
3053:
3052:grid have only
3028:
3027:
3012:
2993:
2992:
2968:
2967:
2946:
2933:
2913:
2912:
2911:
2885:
2874:
2873:
2871:
2840:
2839:
2832:
2805:
2804:
2772:
2761:
2760:
2735:
2734:
2701:
2700:
2689:
2659:
2658:
2656:
2653:polynomial-time
2602:
2601:
2599:
2549:
2548:
2547:
2528:
2527:
2526:having at most
2508:
2507:
2506:For point sets
2479:
2478:
2476:
2455:
2454:
2452:
2433:
2432:
2411:
2410:
2408:
2365:
2364:
2340:
2339:
2337:
2314:
2309:
2277:
2258:
2257:
2256:
2224:
2219:
2218:
2216:
2193:
2192:
2172:
2171:
2138:
2137:
2135:
2111:
2110:
2108:
2089:
2088:
2083:vertices and a
2065:
2064:
2029:
1985:
1984:
1962:
1961:
1922:
1918:
1904:
1903:
1879:
1878:
1876:
1846:
1845:
1842:
1812:
1811:
1786:
1785:
1783:
1761:
1760:
1757:
1705:
1704:
1703:
1676:
1675:
1656:
1655:
1626:
1625:
1623:
1604:
1603:
1574:
1573:
1571:
1544:
1543:
1498:
1497:
1470:
1469:
1437:
1436:
1402:
1401:
1380:
1379:
1377:
1358:
1357:
1332:
1331:
1329:
1310:
1309:
1284:
1283:
1258:
1257:
1238:
1237:
1204:
1203:
1202:
1178:
1177:
1156:
1142:
1141:
1140:
1121:
1120:
1097:
1096:
1091:, published by
1064:
1063:
1048:
1047:
1045:
1013:
1008:
1007:
976:
975:
927:
926:
925:
902:
901:
880:
866:
865:
864:
837:
836:
835:
816:
815:
790:
789:
770:
769:
762:
737:
736:
734:
713:
712:
710:
707:
702:
692:
667:
666:
663:
653:
623:
622:
620:
601:
600:
578:
577:
573:
554:
553:
528:
527:
505:
504:
483:
482:
480:
446:
445:
443:
432:
431:
430:
423:
422:
415:
408:
401:
394:
387:
380:
373:
366:
359:
352:
345:
338:
331:
324:
317:
307:
298:
296:Small instances
255:
254:
252:
222:
221:
199:
198:
177:
176:
174:
155:
154:
132:
131:
99:
98:
76:
75:
39:
38:
19:
12:
11:
5:
4930:
4928:
4920:
4919:
4914:
4909:
4907:Lattice points
4904:
4894:
4893:
4890:
4889:
4870:
4859:
4858:External links
4856:
4854:
4853:
4821:Wood, David R.
4817:
4807:(3): 198–204.
4791:
4761:Wood, David R.
4756:
4732:
4686:Wood, David R.
4681:
4657:
4621:(1): 217–221.
4610:
4584:(2): 355–364.
4569:
4567:. p. 130.
4553:
4511:
4480:
4460:(1): 126–127.
4443:
4430:
4404:(1): 500–518.
4387:
4367:(1–2): 89–90.
4347:
4335:(3): 336–341.
4318:
4298:(4): 527–531.
4278:
4256:
4220:(4): 277–296.
4205:
4193:(1): 108–113.
4176:
4164:(2): 305–311.
4147:
4135:
4088:
4060:(3): 553–579.
4048:Wood, David R.
4040:Dujmović, Vida
4036:
4013:
3992:Dudeney, Henry
3988:
3968:(3): 363–364.
3951:
3915:(2): 169–175.
3891:
3855:(3): 213–221.
3842:
3828:
3807:
3787:(2): 117–130.
3762:
3742:(3): 365–366.
3725:
3676:
3650:
3648:
3645:
3643:
3642:
3630:
3618:
3606:
3602:Klarreich 2016
3594:
3582:
3570:
3551:
3539:
3527:
3515:
3503:
3488:
3473:
3461:
3449:
3437:
3425:
3412:
3400:
3388:
3375:
3358:
3322:
3310:
3291:
3275:
3262:
3260:
3257:
3256:
3255:
3247:
3244:
3228:
3225:
3222:
3219:
3216:
3213:
3210:
3189:
3186:
3183:
3162:
3159:
3132:
3129:
3126:
3123:
3120:
3096:vertices. The
3085:
3080:
3076:
3072:
3068:
3064:
3061:
3041:
3038:
3035:
3000:
2978:
2975:
2953:
2949:
2945:
2940:
2936:
2932:
2929:
2926:
2923:
2920:
2897:
2892:
2888:
2884:
2881:
2859:
2856:
2853:
2850:
2847:
2831:
2828:
2815:
2812:
2792:
2787:
2783:
2779:
2775:
2771:
2768:
2748:
2745:
2742:
2714:
2711:
2708:
2697:Martin Gardner
2688:
2685:
2666:
2638:
2632:
2628:
2624:
2618:
2615:
2612:
2609:
2585:
2579:
2575:
2571:
2565:
2562:
2559:
2556:
2535:
2515:
2486:
2462:
2440:
2418:
2385:
2380:
2375:
2372:
2347:
2313:
2310:
2308:
2305:
2289:
2284:
2280:
2275:
2271:
2268:
2265:
2241:
2237:
2231:
2227:
2213:Pick's theorem
2200:
2179:
2151:
2148:
2145:
2121:
2118:
2096:
2085:graph coloring
2072:
2061:graph coloring
2057:complete graph
2028:
2025:
2013:
2010:
2004:
2000:
1995:
1992:
1972:
1969:
1949:
1946:
1940:
1935:
1929:
1925:
1921:
1914:
1911:
1889:
1886:
1856:
1853:
1841:
1838:
1825:
1822:
1819:
1793:
1771:
1768:
1756:
1753:
1739:
1736:
1733:
1730:
1727:
1724:
1718:
1715:
1691:
1687:
1683:
1663:
1641:
1637:
1633:
1611:
1589:
1585:
1581:
1560:
1557:
1554:
1551:
1528:
1524:
1520:
1517:
1514:
1511:
1508:
1505:
1485:
1481:
1477:
1450:
1447:
1444:
1435:points in the
1424:
1421:
1418:
1415:
1412:
1409:
1387:
1365:
1339:
1317:
1297:
1294:
1291:
1271:
1268:
1265:
1245:
1223:
1220:
1217:
1214:
1211:
1188:
1185:
1163:
1159:
1155:
1152:
1149:
1128:
1104:
1087:A solution of
1071:
1034:
1031:
1028:
1025:
1020:
1016:
995:
992:
989:
986:
983:
974:For instance,
961:
958:
955:
952:
949:
946:
943:
940:
937:
934:
912:
909:
887:
883:
879:
876:
873:
850:
847:
844:
823:
803:
800:
797:
777:
761:
758:
744:
720:
706:
703:
690:
677:
674:
651:
636:
633:
630:
608:
588:
585:
561:
541:
538:
535:
515:
512:
490:
459:
456:
453:
428:
425:
424:
416:
409:
402:
395:
388:
381:
374:
367:
360:
353:
346:
339:
332:
325:
318:
311:
305:
300:
299:
297:
294:
265:
262:
240:
236:
232:
229:
209:
206:
184:
162:
142:
139:
115:
112:
109:
106:
86:
83:
52:
49:
46:
17:
13:
10:
9:
6:
4:
3:
2:
4929:
4918:
4915:
4913:
4910:
4908:
4905:
4903:
4902:Combinatorics
4900:
4899:
4897:
4885:
4884:
4879:
4876:
4871:
4867:
4862:
4861:
4857:
4849:
4844:
4840:
4836:
4835:
4830:
4822:
4818:
4814:
4810:
4806:
4802:
4801:
4796:
4792:
4788:
4784:
4780:
4776:
4772:
4768:
4767:
4762:
4759:Pór, Attila;
4757:
4745:
4741:
4737:
4733:
4729:
4725:
4721:
4717:
4713:
4709:
4704:
4699:
4695:
4691:
4687:
4682:
4677:
4672:
4668:
4667:
4662:
4658:
4654:
4650:
4646:
4642:
4638:
4634:
4629:
4624:
4620:
4616:
4611:
4607:
4603:
4599:
4595:
4591:
4587:
4583:
4579:
4570:
4566:
4562:
4558:
4554:
4550:
4546:
4542:
4538:
4534:
4530:
4529:
4524:
4523:Szemerédi, E.
4520:
4516:
4512:
4508:
4504:
4500:
4496:
4492:
4488:
4487:
4481:
4477:
4473:
4468:
4463:
4459:
4455:
4454:
4449:
4444:
4440:
4436:
4431:
4427:
4423:
4419:
4415:
4411:
4407:
4403:
4400:(in German).
4399:
4398:
4393:
4388:
4384:
4380:
4375:
4370:
4366:
4362:
4361:
4356:
4352:
4348:
4343:
4338:
4334:
4330:
4329:
4324:
4319:
4315:
4311:
4306:
4301:
4297:
4293:
4292:
4287:
4283:
4279:
4275:
4271:
4267:
4266:
4261:
4257:
4253:
4249:
4245:
4241:
4237:
4233:
4228:
4223:
4219:
4215:
4211:
4206:
4201:
4196:
4192:
4188:
4187:
4182:
4177:
4172:
4167:
4163:
4159:
4158:
4153:
4148:
4144:
4140:
4136:
4132:
4128:
4123:
4118:
4113:
4108:
4104:
4100:
4099:
4094:
4089:
4085:
4081:
4077:
4073:
4068:
4063:
4059:
4055:
4054:
4049:
4045:
4041:
4037:
4033:
4029:
4025:
4021:
4020:
4014:
4011:
4007:
4001:
3997:
3993:
3989:
3985:
3981:
3976:
3971:
3967:
3963:
3962:
3957:
3952:
3948:
3944:
3940:
3936:
3932:
3928:
3923:
3918:
3914:
3910:
3909:
3901:
3897:
3892:
3888:
3884:
3880:
3876:
3872:
3868:
3863:
3858:
3854:
3850:
3849:
3843:
3839:
3835:
3831:
3825:
3821:
3817:
3813:
3808:
3804:
3800:
3795:
3790:
3786:
3782:
3781:
3776:
3772:
3768:
3763:
3759:
3755:
3750:
3745:
3741:
3737:
3736:
3731:
3726:
3722:
3718:
3713:
3708:
3703:
3698:
3694:
3690:
3686:
3682:
3677:
3673:
3669:
3665:
3661:
3657:
3652:
3651:
3646:
3639:
3634:
3631:
3627:
3622:
3619:
3615:
3610:
3607:
3603:
3598:
3595:
3591:
3586:
3583:
3579:
3574:
3571:
3568:
3564:
3560:
3555:
3552:
3548:
3543:
3540:
3536:
3531:
3528:
3524:
3519:
3516:
3512:
3507:
3504:
3501:
3500:Eppstein 2018
3497:
3492:
3489:
3485:
3484:Eppstein 2018
3480:
3478:
3474:
3470:
3465:
3462:
3458:
3453:
3450:
3446:
3441:
3438:
3434:
3429:
3426:
3422:
3416:
3413:
3409:
3404:
3401:
3397:
3392:
3389:
3385:
3379:
3376:
3372:
3368:
3362:
3359:
3355:
3351:
3347:
3343:
3342:Anderson 1979
3339:
3335:
3332:; Kløve
3331:
3326:
3323:
3319:
3314:
3311:
3307:
3302:
3300:
3298:
3296:
3292:
3288:
3284:
3279:
3276:
3272:
3267:
3264:
3258:
3253:
3250:
3249:
3245:
3243:
3223:
3220:
3217:
3208:
3187:
3184:
3181:
3172:
3168:
3160:
3158:
3151:
3147:
3130:
3127:
3124:
3121:
3118:
3109:
3107:
3106:finite fields
3103:
3102:vector spaces
3099:
3078:
3074:
3070:
3066:
3059:
3039:
3036:
3033:
3025:
3021:
3016:
2998:
2973:
2951:
2947:
2943:
2938:
2934:
2930:
2927:
2924:
2921:
2890:
2886:
2857:
2854:
2851:
2848:
2845:
2837:
2829:
2827:
2813:
2810:
2785:
2781:
2777:
2773:
2746:
2743:
2740:
2732:
2728:
2712:
2709:
2706:
2698:
2694:
2686:
2684:
2682:
2664:
2654:
2626:
2613:
2610:
2607:
2573:
2560:
2557:
2554:
2533:
2513:
2504:
2502:
2484:
2460:
2438:
2416:
2406:
2401:
2399:
2378:
2370:
2363:
2345:
2335:
2331:
2327:
2323:
2319:
2311:
2306:
2304:
2282:
2278:
2273:
2269:
2239:
2235:
2229:
2225:
2214:
2198:
2177:
2169:
2164:
2149:
2146:
2143:
2119:
2116:
2094:
2086:
2070:
2062:
2058:
2054:
2053:utility graph
2050:
2049:line segments
2046:
2042:
2038:
2037:graph drawing
2034:
2026:
2024:
2011:
2008:
2002:
1998:
1993:
1990:
1970:
1967:
1947:
1944:
1938:
1933:
1927:
1923:
1919:
1912:
1909:
1887:
1884:
1874:
1870:
1854:
1851:
1839:
1837:
1823:
1820:
1817:
1809:
1791:
1769:
1766:
1754:
1752:
1734:
1728:
1725:
1722:
1716:
1713:
1689:
1685:
1681:
1661:
1639:
1635:
1631:
1609:
1587:
1583:
1579:
1558:
1555:
1552:
1549:
1542:
1526:
1522:
1515:
1512:
1509:
1503:
1483:
1479:
1475:
1467:
1462:
1448:
1445:
1442:
1419:
1413:
1410:
1407:
1385:
1363:
1355:
1337:
1315:
1295:
1292:
1289:
1269:
1266:
1263:
1243:
1221:
1218:
1215:
1212:
1209:
1183:
1161:
1157:
1153:
1150:
1126:
1119:, the set of
1118:
1102:
1094:
1090:
1069:
1032:
1029:
1026:
1023:
1018:
1014:
990:
987:
984:
959:
956:
953:
950:
947:
944:
941:
938:
935:
932:
907:
885:
881:
877:
874:
848:
845:
842:
821:
801:
798:
795:
775:
766:
759:
757:
742:
718:
704:
700:
695:
689:
675:
672:
661:
656:
650:
634:
631:
628:
606:
586:
583:
559:
539:
536:
533:
513:
510:
488:
477:
475:
457:
454:
451:
441:
437:
436:Henry Dudeney
303:
295:
293:
291:
287:
286:graph drawing
283:
278:
263:
260:
238:
234:
230:
227:
207:
204:
182:
160:
140:
137:
129:
113:
110:
107:
104:
84:
81:
72:
70:
69:Henry Dudeney
66:
50:
47:
44:
36:
32:
23:
16:
4881:
4841:(1): 25–28.
4838:
4832:
4804:
4798:
4770:
4766:Algorithmica
4764:
4748:. Retrieved
4743:
4736:Pegg, Ed Jr.
4693:
4689:
4664:
4618:
4614:
4581:
4577:
4564:
4535:(1): 13–24.
4532:
4526:
4493:(1): 82–83.
4490:
4489:. Series A.
4484:
4457:
4456:. Series A.
4451:
4438:
4401:
4395:
4364:
4358:
4332:
4331:. Series A.
4326:
4295:
4289:
4263:
4217:
4213:
4190:
4189:. Series A.
4184:
4161:
4160:. Series A.
4155:
4142:
4102:
4096:
4057:
4051:
4026:(1): 26–58.
4023:
4017:
4009:
3999:
3965:
3964:. Series A.
3959:
3922:math/0408396
3912:
3906:
3852:
3846:
3819:
3784:
3778:
3739:
3738:. Series A.
3733:
3692:
3688:
3655:
3633:
3621:
3609:
3597:
3585:
3573:
3554:
3542:
3530:
3518:
3506:
3491:
3464:
3452:
3440:
3428:
3415:
3403:
3391:
3378:
3361:
3325:
3318:Dudeney 1917
3313:
3306:Gardner 1976
3282:
3278:
3266:
3164:
3110:
3017:
2833:
2690:
2505:
2402:
2315:
2165:
2033:degeneracies
2030:
2027:Applications
1843:
1758:
1463:
1352:Because the
1308:grid, where
1139:grid points
1117:prime number
1086:
708:
664:
478:
433:
279:
73:
30:
28:
15:
4912:Conjectures
4795:Roth, K. F.
4661:Pach, János
4006:p. 222
3812:Pach, János
3767:Lubiw, Anna
3590:Jarník 1926
3155:N = 2, 3, 4
3020:hypersphere
2330:approximate
1873:upper bound
1755:Upper bound
1093:Roth (1951)
619:, starting
288:and to the
4896:Categories
4773:(4): 481.
4744:Math Games
4515:Komlós, J.
4282:Guy, R. K.
4227:1508.01097
4105:: 93–128.
4067:cs/0406024
4044:Morin, Pat
4004:Solution,
3702:2203.13170
3647:References
3578:Elkin 2011
3287:Knuth 2008
1089:Paul Erdős
788:points in
440:chessboard
4883:MathWorld
4787:209841346
4703:1208.5289
4628:1406.6713
4519:Pintz, J.
4426:117747514
4112:0801.4310
3862:1206.5350
3721:249687906
3457:Roth 1951
3445:Wood 2005
3421:Pegg 2005
3384:Roth 1951
3185:×
3169:by using
3128:×
3122:×
3037:×
2880:Θ
2855:×
2849:×
2767:Ω
2744:−
2710:×
2608:ℓ
2555:ℓ
2534:ℓ
2264:Ω
2226:ε
2199:ε
2009:≈
1999:π
1945:≈
1924:π
1821:≤
1726:−
1541:hyperbola
1513:−
1446:×
1411:−
1293:×
1267:×
1213:≤
1030:≅
957:−
951:…
799:×
537:×
48:×
4823:(2005).
4750:June 25,
4653:40210322
4559:(2008).
4274:24950467
4252:47260245
3994:(1917).
3947:11035679
3898:(2005).
3814:(2005).
3773:(2007).
3246:See also
2727:superset
2334:APX-hard
2041:vertices
1759:At most
251:points,
74:At most
4728:7164626
4720:3111653
4645:3404483
4606:3935268
4598:3774457
4549:0645860
4507:0525088
4476:0462998
4418:1544776
4383:0974815
4314:0238765
4244:3766097
4131:2823971
4084:3264071
4010:Tribune
3984:0406804
3939:2153735
3838:2163782
3803:2278011
3758:0555806
3672:0349396
3157:, etc.
3150:A280537
3148::
3098:cap set
3013:3 mod 4
2326:NP-hard
1750:points.
697:in the
694:A000769
658:in the
655:A000755
4785:
4726:
4718:
4651:
4643:
4604:
4596:
4547:
4505:
4474:
4439:Quanta
4424:
4416:
4381:
4312:
4272:
4250:
4242:
4129:
4082:
3982:
3945:
3937:
3887:887220
3885:
3877:
3836:
3826:
3801:
3756:
3719:
3670:
2991:where
2217:least
2012:1.814.
1948:1.874.
1602:where
574:to 46,
65:slopes
4783:S2CID
4724:S2CID
4698:arXiv
4649:S2CID
4623:arXiv
4602:S2CID
4422:S2CID
4270:JSTOR
4248:S2CID
4222:arXiv
4107:arXiv
4080:S2CID
4062:arXiv
3943:S2CID
3917:arXiv
3903:(PDF)
3883:S2CID
3875:JSTOR
3857:arXiv
3717:S2CID
3697:arXiv
3259:Notes
3167:torus
3161:Torus
3104:over
2453:size
2409:size
2338:size
2136:with
2087:with
2045:edges
1983:with
1902:with
1877:than
1784:size
1572:(mod
1330:most
1115:is a
621:from
444:case
4752:2012
3824:ISBN
3371:1998
3367:1992
3354:1998
3350:1992
3338:1979
3334:1978
3153:for
3146:OEIS
2966:mod
1624:mod
1219:<
1201:for
1176:mod
1062:mod
924:for
900:mod
699:OEIS
660:OEIS
649:are
253:not
29:The
4843:doi
4809:doi
4775:doi
4708:doi
4671:doi
4633:doi
4619:339
4586:doi
4537:doi
4495:doi
4462:doi
4406:doi
4369:doi
4337:doi
4300:doi
4232:doi
4195:doi
4166:doi
4117:doi
4103:184
4072:doi
4028:doi
3970:doi
3927:doi
3867:doi
3853:121
3789:doi
3744:doi
3707:doi
3693:108
3660:doi
3212:gcd
2872:is
2657:of
2600:to
2477:on
2316:In
2109:to
2035:in
1378:to
735:to
711:of
572:up
481:of
175:to
173:up
33:in
4898::
4880:.
4839:30
4837:.
4831:.
4805:26
4803:.
4781:.
4771:47
4769:.
4742:.
4722:.
4716:MR
4714:.
4706:.
4694:27
4692:.
4647:.
4641:MR
4639:.
4631:.
4617:.
4600:.
4594:MR
4592:.
4582:34
4580:.
4563:.
4545:MR
4543:.
4533:25
4531:.
4521:;
4517:;
4503:MR
4501:.
4491:26
4472:MR
4470:.
4458:24
4450:.
4437:.
4420:.
4414:MR
4412:.
4402:24
4379:MR
4377:.
4365:73
4363:.
4333:18
4325:.
4310:MR
4308:.
4296:11
4294:.
4288:.
4246:.
4240:MR
4238:.
4230:.
4218:27
4216:.
4191:81
4183:.
4162:60
4154:.
4127:MR
4125:.
4115:.
4101:.
4095:.
4078:.
4070:.
4058:34
4056:.
4046:;
4042:;
4024:32
4022:.
3998:.
3980:MR
3978:.
3966:20
3958:.
3941:.
3935:MR
3933:.
3925:.
3911:.
3905:.
3881:.
3873:.
3865:.
3851:.
3834:MR
3832:.
3818:.
3799:MR
3797:.
3785:36
3783:.
3777:.
3769:;
3754:MR
3752:.
3740:27
3732:.
3715:.
3705:.
3691:.
3687:.
3668:MR
3666:.
3565:;
3561:;
3498:;
3476:^
3369:,
3352:,
3344:;
3340:;
3336:,
3294:^
2695:,
2683:.
2503:.
1824:46
1600:),
1082:).
1070:11
1027:16
849:11
802:12
796:12
776:11
701:).
662:).
292:.
183:46
4886:.
4868:.
4851:.
4845::
4827:k
4815:.
4811::
4789:.
4777::
4754:.
4730:.
4710::
4700::
4679:.
4673::
4655:.
4635::
4625::
4608:.
4588::
4574:m
4551:.
4539::
4509:.
4497::
4478:.
4464::
4441:.
4428:.
4408::
4385:.
4371::
4345:.
4339::
4316:.
4302::
4276:.
4254:.
4234::
4224::
4203:.
4197::
4174:.
4168::
4133:.
4119::
4109::
4086:.
4074::
4064::
4034:.
4030::
3986:.
3972::
3949:.
3929::
3919::
3913:9
3889:.
3869::
3859::
3840:.
3805:.
3791::
3760:.
3746::
3723:.
3709::
3699::
3674:.
3662::
3640:.
3628:.
3616:.
3604:.
3592:.
3580:.
3549:.
3537:.
3525:.
3513:.
3486:.
3471:.
3459:.
3447:.
3435:.
3410:.
3398:.
3386:.
3373:.
3356:.
3320:.
3308:.
3289:.
3273:.
3239:.
3227:)
3224:n
3221:,
3218:m
3215:(
3209:2
3188:n
3182:m
3131:N
3125:N
3119:N
3084:)
3079:3
3075:/
3071:2
3067:n
3063:(
3060:O
3040:n
3034:n
2999:p
2989:,
2977:)
2974:p
2952:2
2948:y
2944:+
2939:2
2935:x
2931:,
2928:y
2925:,
2922:x
2919:(
2908:.
2896:)
2891:2
2887:n
2883:(
2858:n
2852:n
2846:n
2814:n
2811:2
2791:)
2786:3
2782:/
2778:2
2774:n
2770:(
2747:1
2741:n
2713:n
2707:n
2677:,
2665:S
2649:.
2637:)
2631:|
2627:S
2623:|
2617:(
2614:O
2611:=
2596:,
2584:)
2578:|
2574:S
2570:|
2564:(
2561:O
2558:=
2514:S
2497:.
2485:k
2473:,
2461:n
2439:k
2429:,
2417:k
2384:)
2379:k
2374:(
2371:O
2358:,
2346:k
2300:.
2288:)
2283:2
2279:n
2274:/
2270:1
2267:(
2252:,
2240:2
2236:/
2230:2
2178:n
2162:.
2150:n
2147:=
2144:k
2132:.
2120:k
2117:n
2095:k
2071:n
2003:3
1994:=
1991:c
1971:n
1968:c
1939:3
1934:3
1928:2
1920:2
1913:=
1910:c
1900:,
1888:n
1885:c
1855:n
1852:2
1818:n
1804:.
1792:n
1770:n
1767:2
1738:)
1735:n
1732:(
1729:o
1723:n
1717:2
1714:3
1690:2
1686:/
1682:n
1662:n
1652:.
1640:2
1636:/
1632:n
1610:k
1588:2
1584:/
1580:n
1559:k
1556:=
1553:y
1550:x
1527:2
1523:/
1519:)
1516:2
1510:n
1507:(
1504:3
1484:2
1480:/
1476:n
1449:n
1443:n
1423:)
1420:n
1417:(
1414:o
1408:n
1398:,
1386:n
1364:p
1350:.
1338:n
1316:p
1296:n
1290:n
1270:p
1264:p
1244:n
1234:,
1222:n
1216:i
1210:0
1199:,
1187:)
1184:n
1162:2
1158:i
1154:,
1151:i
1148:(
1127:n
1103:n
1046:(
1033:5
1024:=
1019:2
1015:4
994:)
991:5
988:,
985:4
982:(
972:.
960:1
954:p
948:,
945:1
942:,
939:0
936:=
933:i
911:)
908:p
886:2
882:i
878:,
875:i
872:(
861:;
846:=
843:p
822:p
755:.
743:n
731:,
719:n
676:n
673:2
647:,
635:2
632:=
629:n
607:n
587:n
584:2
560:n
540:n
534:n
514:n
511:2
501:,
489:n
470:.
458:8
455:=
452:n
276:.
264:n
261:2
239:2
235:/
231:n
228:3
208:n
205:2
195:,
161:n
141:n
138:2
114:1
111:+
108:n
105:2
85:n
82:2
51:n
45:n
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
