7
$\begingroup$

Question. Consider $n \geq 5$ lines in a general position (i.e. no two lines are parallel and no triple intersections are allowed) in $\mathbb{R}^2$. Let $T(n)$ denote the maximal number of empty triangles (here empty triangle means that it does not contain other triangle). What would be best upper and lower bounds for $T(n)$? I know $(n-2) \leq T(n)$ holds, but I am hoping for a better lower bound. Is it true that $n \leq T(n)$? Also, is it possible to compute $T(n)$ it for small $n$ (where small means $6 \leq n \leq 10$)? I think $T(6) = 6$, but I am not able to show $6$ is an upper bound as well.

$\endgroup$
11
  • 1
    $\begingroup$ $T(n)\ge n$ is also true, taking the $n$ prolongations of the edges of a regular $n$-gone (this produces a triangle on each edge, if $n\ge 5$). $\endgroup$ Aug 21, 2012 at 6:30
  • 6
    $\begingroup$ Finding the best upper bound for T(n) will be no easy task; this is a well known open question in graph theory. A reference to your exact question came up in a 2011 Stanford Programming Contest. See part E (pdf p. 11/17) in cs.stanford.edu/group/acm/SLPC/problems.pdf. $\endgroup$ Aug 21, 2012 at 7:35
  • 2
    $\begingroup$ @gotmath: that's already clear with $n=5$. Five lines in generic position can produce 3, 4 or 5 triangles, according to their position. $\endgroup$ Aug 21, 2012 at 8:52
  • 1
    $\begingroup$ Also, $T(n)\ge n$ is certainly not optimal. Just playing with $6,7,$ and $8$ lines I obtained partitions of the plane having respectively $7, 10,$ and $13$ triangular components. I wouldn't find it surprising that $T(n)/n\to\infty$. $\endgroup$ Aug 21, 2012 at 14:04
  • 1
    $\begingroup$ $T(n)$ should grow at least quadratically in $n$. Consider a configuration along the lines of all the lines of the form $x=k$, $y=k$ or $x+y=k+1/2$, where $k<n/6$. All the lattice points $(x,y)$ with $|x|+|y|<n/6$ are involved in triangles with $(x,y+1/2), (x+1/2,y)$ and $(x,y-1/2), (x-1/2,y)$. $\endgroup$ Aug 21, 2012 at 21:41

2 Answers 2

4
$\begingroup$

You can easily show that $3k$ lines can be arranged to have at least $\frac34 k^2$ triangles, which proves that asymptotically, $T(n) \ge n^2/12$.

The following picture shows the example for $k=4$ -- there are three groups of $k$ lines each, group 1 and group 2 forming a "squarish" $k\times k$ chessboard, which is being then intersected by the lines from group 3. They will produce $(k+1)+(k+1)+k+k+(k-1)+(k-1)+...$ triangles which comes to approximately $\frac34k^2$ triangles. And I am not even counting the ones that these groups will produce far away from the chessboard, inside their "own domain" so to speak.

picture with 3 $k$ lines:

     

$\endgroup$
1
  • $\begingroup$ Actually, we can extend this argument (by carefully adding the triangles formed within groups 1, 2 and 3) and prove that $T(n) \ge n^2/9$ $\endgroup$
    – JimT
    Aug 5, 2017 at 15:32
1
$\begingroup$

The number of empty triangles $T(n)$ is lower bounded by the number of minimum area triangles $m(n)$ for which the asymptotic value is known to be $n^2/6$, see Triangle areas in line arrangements by Gábor Damásdi, Leonardo Martínez-Sandoval, Dániel T. Nagy, Zoltán Lóránt Nagy.

$\endgroup$

Your Answer

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

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