# Numbers of intersection points and lines

Hello,

I don't know if this question has already been posted, I have made a little search with keywords and did not found it, sorry if I missed anything.

Is it possible to characterize the set of pairs of integers ($l$,$i$) such that one can draw $l$ lines on the euclidean plane with exactly $i$ intersection points?

It is quite trivial to see is that given $l$, an upper bound for $i$ is $l(l+1)/2$. More generally, given $l$, any additive decomposition of $l$ of the form $\underset{j=1}{\overset{k}{\sum}} l_i$ provides a value for $i$ which is $\underset{i=1}{\overset{k}{\sum}}$ $\underset{j>i}{\overset{k}{\sum}} l_i l_j$ if we fix for any $i \in [1,k]$ exactly $l_i$ parallel lines such that there is no intersection of three or more lines at the same point.

It is not difficult to see that there are pairs ($l$,$i$) that are not of this form. For instance, if you try all decompositions of 6, you may draw 6 lines with 5, 8, 9, 11, 12, 13, 14 or 15 intersection points with this method, but 7 and 10 are missing (they can be obtained with intersection points of three lines).

Here is a link containing some observations (http://www.ics.uci.edu/~eppstein/junkyard/how-many-intersects.html). As far as I know, this is the only place where this problem has been seriously considered, but it is quite old and maybe lacks of results. So any additional comment will be welcomed :)

Just a final remark, thanks to some projective properties, this question is the same as finding $c$ circles sharing a common point with exactly $i+1$ intersection points. Don't know if this can help.

-
The expert on this topic is Branko Grünbaum, who recently summarized his extensive knowledge in the book, Configurations of Points and Lines: ams.org/bookstore-getitem/item=GSM-103 . –  Joseph O'Rourke Dec 4 '11 at 14:47
So if you count points of infinity, each pair of lines must intersect one. The intersection of $k$ lines has multiplicity $k(k-1)/2$. Also your upper bound for $l$ lines should probably be $l(l-1)/2$. So you take $l(l-1)/2$, partition it into smaller triangular numbers, throw out the ones at infinity, and count the remaining ones. –  Will Sawin Dec 4 '11 at 19:16
@Will: Easier said than done. –  Igor Rivin Dec 4 '11 at 19:49
A related question is to characterize the pairs $(\ell,r)$ such that one can draw $\ell$ lines in the plane dividing the plane into exactly $r$ regions. This was discussed at math.stackexchange.com/questions/38350/… and, given Euler's formula, perhaps some of the discussion and references there would be relevant. –  Gerry Myerson Dec 4 '11 at 22:23
Thanks Joseph for the book however it won't be possible for me to read it :/ You're right Will, that's l(l-1)/2, not l(l+1)/2 Thanks Gerry for this discussion, I will take a look at this, maybe this can help –  Nekochan Dec 5 '11 at 12:28

In the paper below we characterize for large $n$ the possible values of the number of connecting lines determined by a set of $P_n$ points in the plane, where a connecting line is any straight line containing at least two points of $P_n$. This solves a problem posed by Grünbaum [5,6] which asks for the sequence of all integers $m$ with the property that some configuration of $n$ points determine exactly $m$ lines.
([6] is Arrangements and Spreads; [5] is Erdős's earlier partial solution.) They obtain exact expressions "for the lower end of the continuum of values leading down from $\binom{n}{2}-4$." "The possible values...can be seen to bear a strong resemblance to physical spectra." The lower end of the continuum grows as $n^{3/2}$ (with constant 1). Here are two figures from the paper:
Joseph, can you elaborate on the nature of the duality here? It seems to me there might be something at stake in the difference. In particular, it's easy to get $n$ lines to have zero points of intersection, but a lot harder to get $n$ points to determine less than one line. –  Barry Cipra Dec 8 '11 at 19:25
@Barry: I think the distinction only occurs in the Euclidean plane, but in the projective plane, $n$ "parallel" lines meet at one point at infinity, and $n$ collinear points determine just one line. –  Joseph O'Rourke Dec 9 '11 at 0:29