1
$\begingroup$

Suppose we have $n$ lines in plane which is divided equally among the three sets(the lines in each set are equally spaced), each of contains $n/3$ lines. And they intersect each other and creates a triple intersection.

enter image description here

My question is how can I prove that there are $\Theta(n^2)$ triple intersections?

$\endgroup$
6
  • $\begingroup$ Can you add other assumptions? All we have is a picture. We cannot bound the number of triples from below by a quadratic if each set of lines follows an edge of a triangle, for example. If each set consists of parallel lines, then it is easy to show that there are at most quadratic number of triples. $\endgroup$ Commented Aug 20 at 18:18
  • $\begingroup$ @BaderAbuRadi Yes, you consider each set consists of parallel lines for sake of simplicity. Note that almost two vertical lines sets creates quadrilateral which is rhombus, but horizontal lines through vertices of rhombus creates two triangles and four triple intersections. $\endgroup$
    – user150715
    Commented Aug 20 at 18:28
  • 3
    $\begingroup$ @BaderAbuRadi Though even if the lines are not parallel, there are $O(n^2)$ (double) intersections (also easily provable: at step $n$ there are $n-1$ lines on the plane, so a new line can only intersect at most $n-1$ lines) and since triple intersections are only a subset of intersections, the same upper bound follows for them. $\endgroup$
    – rus9384
    Commented Aug 20 at 21:19
  • $\begingroup$ @rus9384 Right, for the upper bound there is no need to have the parallel assumption. $\endgroup$ Commented Aug 20 at 21:27
  • $\begingroup$ Is there any sense in which this requires answers from a computer science perspective? It seems like a matter of pure mathematics. $\endgroup$
    – D.W.
    Commented Aug 20 at 21:38

2 Answers 2

3
$\begingroup$

This is in no way formal, it is based on the assumptions and intuition given by the asker in the comments, and under the assumption that $\frac{n}{3}$ is odd. The middle horizontal line $l_0$ crosses $\frac{n}{3} -1$ rhombus, where each pair of parallel edges of a rhombus are induced by two adjacent lines from the same vertical set. The horizontal lines $l_1$ and $l_2$, above and below $l_0$, respectively, cross $\frac{n}{3} - 2$ rhombus each. Proceeding similarly, we get the horizontal line $l_3$ above $l_1$, and the horizontal line $l_4$ below $l_2$ cross $\frac{n}{3} - 3$ rhombus each. Proceeding iteratively, and assuming $\frac{n}{3}$ is odd, we get that the number of rhombus crossed horizontally is $$ (\frac{n}{3} -1) + 2\cdot \sum\limits_{i=2}^{\frac{\frac{n}{3} - 1}{2}} (\frac{n}{3} - i)$$

As the the number of triples each horizontal lines passed through equals the number of rhombus it crosses plus one, we get that the number of triples is

$$ \frac{n}{3} + 2\cdot \sum\limits_{i=2}^{\frac{\frac{n}{3} - 1}{2}} (\frac{n}{3} - i + 1) = \theta(n^2)$$

$\endgroup$
0
4
$\begingroup$

The lines define a tiling of a regular hexagon with equilateral triangles. If you add two lines symmetrically to all three pencils, the size of the hexagon grows by one layer.

When the number of lines grows linearly, the number of triangles, as well as the number of vertices (by the Euler relation), grows as an area, i.e. quadratically.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.