2
$\begingroup$

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):

line $l$ intersects $(n-2)*2$ edges

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

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.