# Tight bound on the number of intersections between a line and a triangulation

I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of intersections that any line could have with any triangulation on any point set.

There is an upper bound of $2n-5$ on the number of triangles for Delaunay triangulations, this implies an upper bound on the number of triangles for any triangulation, since any triangulation can be turned into a Delaunay triangulation using flips which don't change the number of triangles.

The first obvious upper bound is $3\cdot(2n-5)$ since there are at most $3$ edges per triangle. The next better obvious one is $2\cdot(2n-5)$ since a line can intersect at most $2$ edges of a triangle.

My current best lower bound (and I suspect that this is tight) on the number of intersections is $(n-2)\cdot2$ based on the following example (ignore the arrows, for every point added to the bottom we obtain 2 additional intersections by connecting it to the two top ones):

How to prove (or disprove) that the upper bound is $(n-2)\cdot2$?

## 1 Answer

Place $T$ triangles next to each other such that the line $l$ intersects them all. Observe how the number of intersections is $T+1$. Now substitute $T$ with the upper bound on the number of triangles for any triangulation that you mentioned, and we obtain $2n-5+1=2n-4$ as an upper bound on the number of intersections. The example provided in the question shows that the bound is tight.