# $n$ lines in a general position and the number of empty triangles

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.

• $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$). – Pietro Majer Aug 21 '12 at 6:30
• 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. – Benjamin Dickman Aug 21 '12 at 7:35
• @gotmath: that's already clear with $n=5$. Five lines in generic position can produce 3, 4 or 5 triangles, according to their position. – Pietro Majer Aug 21 '12 at 8:52
• 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$. – Pietro Majer Aug 21 '12 at 14:04
• $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)$. – Kevin P. Costello Aug 21 '12 at 21:41

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.
• 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$ – JimT Aug 5 '17 at 15:32