1
$\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
$\begingroup$

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

enter image description here


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

enter image description here

$\endgroup$
5
  • $\begingroup$ @AnnaVopureta added some more thoughts and two "worse" examples. $\endgroup$
    – Joffan
    Dec 4 '17 at 23:50
  • $\begingroup$ Your examples are providing lower bounds for the number of intersections a line can have when "shot" through a triangulation of a simple polygon with $n$ vertices. I'm interested in upper bounds, as in: any triangulation has at most $2n -5$ triangles, we can't have more than $3$ intersections per triangle, hence $3*(2n-5)$ is an example upper bound (a bad one since a line can't intersect all 3 edges of a triangle). The goal is to arrive at an upper bound and prove that it's tight by providing an example that achieves the number of intersections provided by the bound $\endgroup$ Dec 5 '17 at 12:15
  • $\begingroup$ I edited the question to include my current thoughts. $\endgroup$ Dec 5 '17 at 13:34
  • $\begingroup$ I request that you upvote this answer, since it has clearly helped you already, and I will consider adding another answer to your extensive revisions. $\endgroup$
    – Joffan
    Dec 5 '17 at 13:57
  • $\begingroup$ Looking forward to your thoughts on the current lower (and hopefully upper) bound of $(n-2)\cdot2$ intersections. $\endgroup$ Dec 5 '17 at 14:26
0
$\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$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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