using points to create lines

The maximum number of lines $\mathcal{N}$ is $10$.

This number $10$ is achieved by following configuration:

ten 3-point-lines through nine points

This bounds $\mathcal{N}$ from below by $10$.

For an upper bound, let $S \subset \mathbb{R}^2$ be any set of $n \ge 3$ points in the plane and $L$ be the collection of lines containing at least 2 points from $S$.

Out of these $n$ points, we can form $\frac12 n(n-1)$ pairs from them. For any line in $L$, if it contains $m$ points from $S$, it will contain $\frac12 m(m-1)$ pairs. Notice a pair uniquely determine a line, this means the set of pairs associated with different lines in $L$ are disjoint. If we let $N_m$ be the number of lines containing $m$ points from $S$, we have:

$$\frac{n(n-1)}{2} = \sum_{m \ge 2} N_m \frac{m(m-1)}{2}\tag{*1}$$

This leads to $\quad\displaystyle\frac{n(n-1)}{2} \ge N_2 + 3 N_{\ge 3}\quad$ where $\quad N_{\ge 3} \stackrel{def}{=} \sum\limits_{m\ge 3} N_m$.
In $1958$, Kelly and Moser has shown$\color{blue}{{}^{[1]}}$:

If $S$ doesn't lie on a single line, then $N_2 \ge \frac{3n}{7}$.

For the problem at hand, we have $n = 9$. Above result implies

$$N_{\ge 3} \le \frac13 \left(\frac{9(9-1)}{2} - \frac{3(9)}{7}\right) = \frac{75}{7}$$ Since LHS is an integer, we find $N_{\ge 3} \le 10$ unless $S$ lies on a single line. If $S$ lies on a single line, it is clear $N_{\ge 3} = 1$. Combine these, we can conclude out of any set $S$ of $9$ points, we can construct at most $10$ lines which passes through $3$ or more points from $S$.

This establishes the upper bound $\mathcal{N} \le 10$. Combine with the lower bound, we conclude $\mathcal{N} = 10$.

The problem here is related to the orchard-planting problem which asks how to plant $n$ trees so that there will be $r(n,k)$ straight rows with k trees in each row. The variant of finding the maximum number of $3$-point lines for $n$ points is due to Sylvester. Look at Borwein and Moser's survey article$\color{blue}{{}^{[2]}}$ for more info about the Sylvester problem. In particular, it has a proof of the Kelly and Moser's result mentioned above.


Notes/References

  • $\color{blue}{[1]}$ - Kelly, L.M. and Moser, W. 1958. On the number of ordinary lines determined by $n$ points. Canad. J. Math. 10, 210-219. MR: 20, #3494.

  • $\color{blue}{[2]}$ - Borwein, P & O. J. Moser, W. (1990). A survey of Sylvester's problem and its generalizations. Aequationes Mathematicae. 40. 111-135. 10.1007/BF02112289.