种树问题

定义t₃^果园(n)为过n定点可达到的3点线的最大数量。

在1974年，对于任意的正整数点n、t₃^果园(n)被证明是(1/6)n² − O(n)。

第一个t₃^果园(n)的数值在右表中（OEIS数列A003035）.

由于没有两个直线可以共同经过两个不同点，一个平凡的3点线的数量上限由以下n点的情况确定

${\displaystyle \left\lfloor {\binom {n}{2}}{\Big /}{\binom {3}{2}}\right\rfloor =\left\lfloor {\frac {n^{2}-n}{6}}\right\rfloor .}$ 

事实是数的2点线至少是6n/13 （Csima & Sawyer 1993），该上限可以降低到

${\displaystyle \left\lfloor {\frac {{\binom {n}{2}}-6n/13}{3}}\right\rfloor =\left\lfloor {\frac {n^{2}}{6}}-{\frac {25n}{78}}\right\rfloor .}$ 

t₃^果园(n)的下限由通过定点的许多的3点线的构造给出。最早的二次方程式下限-(1/8)n²由西尔维斯特给出，他在三次曲线y = x³放了n个点。这在1974年由 Burr, Grünbaum, and Sloane （1974）采用一个魏尔斯特拉斯椭圆函数基础上的结构改善至[(1/6)n² − (1/2)n] + 1。一个Füredi & Palásti (1984)建立的圆内螺线基本的构造取得了相同的下限。

在2013年九月, Ben Green和陶哲轩发表的一篇论文中，他们证明了所有的点集必然的大小，n > n₀，至多有([n(n - 3)/6]  + 1) = [(1/6)n² − (1/2)n + 1] 3点线，其中相应的下限由Burr, Grünbaum和Sloane确立。^[2] 这有一个比直接从他们的紧的下限得出的2点线的数n/2要略胜一筹的极限：[n(n − 2)/6]，分别由Gabriel Andrew Dirac和Theodore Motzkinproved 在相同的论文中和解决一个1951问题以独立地身份证明。

• Brass, P.; Moser, W. O. J.; Pach, J., Research Problems in Discrete Geometry, Springer-Verlag, 2005, ISBN 0-387-23815-8 .
• Burr, S. A.; Grünbaum, B.; Sloane, N. J. A., The Orchard problem, Geometriae Dedicata, 1974, 2 (4): 397–424, doi:10.1007/BF00147569 .
• Csima, J.; Sawyer, E., There exist 6n/13 ordinary points, Discrete and Computational Geometry, 1993, 9: 187–202, doi:10.1007/BF02189318 .
• Füredi, Z.; Palásti, I., Arrangements of lines with a large number of triangles, Proceedings of the American Mathematical Society, 1984, 92 (4): 561–566, JSTOR 2045427, doi:10.2307/2045427 .
• ^[1]

• 埃里克·韦斯坦因. Orchard-Planting Problem. MathWorld. 

1. ^ Green, Ben; Tao, Terence, On sets defining few ordinary lines, Discrete and Computational Geometry, 2013, 50 (2): 409–468, doi:10.1007/s00454-013-9518-9