Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
4  
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

1 Answer 1

up vote 4 down vote accepted

I asked Jon Lenchner, an expert on point-line incidences, and he told me the question (in dual form) was posed in Grünbaum's 1971 book Arrangements and Spreads, and fully answered in a paper by Peter Salamon and Paul Erdős: "The solution to a problem of Grünbaum," Canad. Math. Bull. 31: 129-138 (1988). Here are its first two sentences:

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:
     SE Fig1
     SE Fig4

share|improve this answer
    
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
1  
@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
    
That's very nice, thanks a lot for this reference! –  Nekochan Dec 11 '11 at 13:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.