2
$\begingroup$

Let $S$ be a set of $n$ lines such that no two are parallel and no three meet in the same point. Show by induction that the lines in $S$ determine $\Theta(n^2)$ intersection points.

I've read the definition of $\Theta(n^2)$, but when I draw these lines on a paper, I don't even get that it is correct that the number of intersection points is $\Theta(n^2)$. Because for 3 lines I get 3 intersection points, for 4 lines I get 6. And for 5 lines, it seems to be 9. So my hypothesis would rather be that it is $3(n-2)$ intersection points... but, of course, the book is correct, in some way...

And for $\Theta$-order, it is both Big-Oh and $\Omega$-order, so I should count $n^2$? Of course, for this "order functions", I may choose an $n_0$ that is the lower bound for $n$ as high as I would like, but it is impossible to visualize this on a drawing, when $n_0$ gets like above 5...

And, besides... counting the points using a drawing is not formal math, so how could I even know how many more intersection points adding a new line would add?

$\endgroup$
2
  • 3
    $\begingroup$ Any two non-parallel lines intersect in exactly one points. If those points are all unique, then how many new intersections does the $n+1$st line add? You should be able to come up with a recursion here. $\endgroup$
    – Malady
    Commented Jun 17 at 0:21
  • $\begingroup$ Yes, I now understand that the n+1 th line will add n new points. So the number of points will be $\sum_{i=2}^n{i-1}$, which is $\Theta(n^2)$. $\endgroup$ Commented Jun 17 at 0:37

1 Answer 1

4
$\begingroup$

Let $S(n)$ be the number of intersections of $n$ non-parallel lines, where no $3$ lines intersect in the same point.

Clearly, $S(1)=0$.

Any pair of non-parallel lines intersect in exactly one point. Thus we can see that the $n+1$st line intersects the previous $n$ lines in exactly $n$ points. By the condition that no three lines intersect in the same point, these new points are all unique. Thus we see: $$S(n+1)=S(n)+n$$ And therefore $$S(n)=\frac{n(n-1)}{2}$$ (it is the sum of the first $n-1$ numbers).

Can you show this is the appropriate complexity?

One last thing which I think is important, if not required for this problem. How do we know such a set of $n$ lines exists? Clearly we can get them to be all non-parallel, since there are uncountably many angles to choose from. And indeed we can also get all the intersections to be unique, since we can draw our $n$th line sufficiently far from all the previous intersections.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .