1
$\begingroup$

The stabbing number of a triangulated simple polygon P is the maximum number of diagonals intersected by any line segment interior to P. Give an algorithm that computes a convex polygon triangulation with stabbing number O(log n).

A convex polygon with n vertex is given, assuming n is even for simplicity. I've already triangulate the polygon taking the vertex v(1) and linking it to the vertex v(3) and so on v(3) to v(5) with the logic of v(i) to v(i+2). In this way I generate a sub polygon using n/2 diagonals and then repeat this process with the sub polygon until I get a triangle. In this way I always triangulate the polygon using n/2 diagonals where n is the number of vertex of the sub polygon.

Now that the polygon in triangulated in O(logn), I got stuck. If I draw a segment inside the triangulated polygon, with the aim of intersect the maximum possible number of diagonals, I always intersect more than logn diagonals. So I assume that what the problem is asking is not to have a precise logn stubbing number, but still I don't have an answer.

$\endgroup$
2
  • $\begingroup$ "the polygon in triangulated in O(logn)": what does that mean ?? Any triangulation takes exactly n-3 diagonals. $\endgroup$
    – user16034
    Feb 10, 2023 at 11:07
  • $\begingroup$ You are asked to fulfill $O(\log n)$, not $\log n$. $\endgroup$
    – user16034
    Feb 10, 2023 at 11:17

2 Answers 2

1
$\begingroup$

In the recursive triangulation you consider, you roughly divide the number of vertices by $2$ at each level of recursion. Thus, there are $O(\log n)$ levels of recursion. Consider some segment $S$. Among all the diagonals added at some level of recursion, $S$ can intersect at most $2$ (try to prove it!), so in total it intersects at most $2\cdot O(\log n) = O(\log n)$ diagonals.

$\endgroup$
1
$\begingroup$

By linking every other vertex, you create an inner convex polygon of $\left\lceil\dfrac n2\right\rceil$ sides, which can only be intersected twice by a line segment. By induction, there will be $O(\log n)$ intersections.

$\endgroup$

Your Answer

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

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