In discrete geometry

Discrete geometry

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles,...

, the original orchard-planting problem asks for the maximum number of 3-point lines attainable by a configuration of points in the plane. Also called the Tree-planting problem, there are investigations into how many 4-, 5- & 6-point lines can be made. A variation is to restrict the plane to a square format such as a chessboard.

Integer sequence

Define t₃^orchard(n) to be the maximum number of 3-point lines attainable with a configuration of n points.
For an arbitrary number of points, n, the exact value of t₃^orchard(n) is generally not known. However, its value is known to be asymptotic

Asymptotic analysis

In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

 to (1/6)n².

The first few values of t₃^orchard(n) are given in the following table .

n	4	5	6	7	8	9	10	11	12	13	14
t3orchard(n)	1	2	4	6	7	10	12	16	19	22	26

Upper and lower bounds

Since no two lines may share two distinct points, a trivial upper-bound for the number of 3-point lines determined by n points is
Using the fact that the number of 2-point lines is at least 6n/13 , this upper bound can be lowered to

Lower bounds for t₃^orchard(n) are given by constructions for sets of points with many 3-point lines. The earliest quadratic lower bound of ~(1/8)n² was given by Sylvester

James Joseph Sylvester

James Joseph Sylvester was an English mathematician. He made fundamental contributions to matrix theory, invariant theory, number theory, partition theory and combinatorics...

. This was improved to ~(1/6)n² more recently by . The best construction known is that of which achieves ⌊(1/6)n² − (1/2)n + 1⌋.