Welcome to MathOverflow

Question

5

1

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.

edited Aug 21 at 5:16

asked Aug 21 at 5:00

gotmath
51●2

1

$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 at 6:30

6

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 at 7:35

1

@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 at 8:52

1

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 at 14:04

1

$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 at 21:41

show 6 more comments

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

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.