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.
-
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 MajerAug 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$– Benjamin DickmanAug 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$– Pietro MajerAug 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$– Pietro MajerAug 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$– Kevin P. CostelloAug 21, 2012 at 21:41
2 Answers
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.
-
$\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$– JimTAug 5, 2017 at 15:32
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.