Convex polygon triangulation with stabbing number O(log n)

Question

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.

Answer 1

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.

Answer 2

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.