Let $P_1$ be a set of 4 points in the Euclidean plane. Formally, $P_1$ determines a set $L_1$ of 6 lines, which then determine only 3 points not already in $P_1.$ Let $P_2$ be the set of 7 points thus far determined. Formally, $P_2$ determines only 3 lines not already in $L_1.$ Let $L_2$ be the set of 9 lines thus far determined. Continuing in this manner determines sets $P_n$ and $L_n.$ What can be said about the cardinalities $|P_n|$ and $|L_n|$?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ I assume you want $P_1$ to be generic; the counts go down if three points are collinear or are vertices of a parallelogram (though the latter degeneracy can be removed by working in the projective plane instead of the Euclidean one: in the projective plane, all $P_1$ in general linear position are equivalent). $\endgroup$– Noam D. ElkiesCommented Jul 18, 2018 at 13:52
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
The question is discussed in Cooper, Joshua; Walters, Mark; Iterated point-line configurations grow doubly-exponentially, Discrete Comput. Geom. 43 (2010), no. 3, 554–562, MR2587837 (2011f:51016). I quote from the review by Tamas Szonyi:
Consider a quadrangle as the starting configuration (stage one). In each stage the process considers the lines joining pairs of points that were constructed in the previous stages and adds the (affine) intersections of these lines. The starting quadrangle has to be in such a general position that no lines in any stage are parallel. The main results of the paper give doubly exponential upper and lower bounds on the number of points at each stage.
A preprint is also available on arXiv. See also https://oeis.org/A140468 and https://oeis.org/A243707. https://arxiv.org/abs/1406.5157 is entertaining.
answered Jul 19, 2018 at 0:24
$\begingroup$
$\endgroup$
As Noam Elkies commented, some arrangements allow for three points on a line, or more than two lines meeting at a newly created point. Combinatorially, and assuming such coincidences do not occur, n points determine $m=\binom{n}{2}$ many lines with each of the $n$ points on $n-1$ distinct lines, and the $m$ lines then determine $m(m -2n+3)/2$ new points, as a line intersects $2n-4$ other lines in its two old points.
However, each new line contains many of the new points, so the above when iterated provides a poor upper bound. If I can, later I will look at point-line incidences to see how to refine the above observations.
Gerhard "Geometric Lattices Can Grow Quickly" Paseman, 2018.07.18.
answered Jul 18, 2018 at 15:06