Upper bound on the number of intersections for a given triangulation

Question

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$?

Answer 1

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.

Answer 2

The intersection line divides the set of $n$ points into two groups, $A$ and $B$.

Traversing this line from the first intersection to the last, any given triangulation line will between two points in $A$ ($a_i$) and $B$ ($b_j$). The next triangulation line can share one of these points (or neither). Say $a_i$ is also an endpoint for the following intersection; that means that $b_j$ cannot be on any future triangulation line intersection, because the triangulation does not intersect itself.

Therefore we irrevocably discard (at least) one point from consideration with every intersection and the maximum number of crossings is therefore $\fbox{$n{-}1$}$ (as we need two points to define each triangulation line).

---

The above argument is good for convex polygons.

Following the example given, it seems there is no particular constant upper bound above $n$ for non-convex polygons, since we can make repeats like this which approach $\frac 43 n$:

---

Hmm, it gets worse. Here's a pattern that tends towards $\frac 32 n$, here at $n=14$ with $18$ intersections.

Answer 3

The general (non-polygon) case has the intersection line dividing the $n$ points into two groups and cutting edges that cross between those two groups.

Thus the maximum number of edges in a planar bipartite graph on $n$ points will give an upper bound on the answer.

Recalling Euler's $e+2=v+f$ for planar graphs, we can find this maximum.

Since all cycles in bipartite graphs are even, so faces (regions) have at least four edges, and every edge contributes to two faces, we have $4f \le 2e$, so $ f \le e/2$. Then $v{-}2 = e{-}f \ge e-e/2 =e/2 $ and thus $e\le 2v-4$, and you have already shown that the equality is possible.