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$
  • 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$ – Pietro Majer Aug 21 '12 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$ – Benjamin Dickman Aug 21 '12 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$ – Pietro Majer Aug 21 '12 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$ – Pietro Majer Aug 21 '12 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$ – Kevin P. Costello Aug 21 '12 at 21:41
2
$\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$
  • $\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 '17 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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