In discrete geometry, the original orchard-planting problem (or the tree-planting problem) asks for the maximum number of 3-point lines attainable by a configuration of a specific number of points in the plane. There are also investigations into how many -point lines there can be. Hallard T. Croft and Paul Erdà Âs proved
where is the number of points and is the number of -point lines. Their construction contains some -point lines, where . One can also ask the question if these are not allowed.
Define to be the maximum number of 3-point lines attainable with a configuration of points. For an arbitrary number of points, was shown to be in 1974.
The first few values of are given in the following table .
Since no two lines may share two distinct points, a trivial upper-bound for the number of 3-point lines determined by points is
Using the fact that the number of 2-point lines is at least , this upper bound can be lowered to
Lower bounds for are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of was given by Sylvester, who placed points on the cubic curve . This was improved to in 1974 by , using a construction based on Weierstrass's elliptic functions. An elementary construction using hypocycloids was found by achieving the same lower bound.
In September 2013, Ben Green and Terence Tao published a paper in which they prove that for all point sets of sufficient size, , there are at most
3-point lines which matches the lower bound established by Burr, Grünbaum and Sloane. Thus, for sufficiently large , the exact value of is known.
This is slightly better than the bound that would directly follow from their tight lower bound of for the number of 2-point lines: proved in the same paper and solving a 1951 problem posed independently by Gabriel Andrew Dirac and Theodore Motzkin.
Orchard-planting problem has also been considered over finite fields. In this version of the problem, the points lie in a projective plane defined over a finite field. .