Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles

Suppose a convex polygon $P$ in plane is given. We want to triangulate it such that any arbitrary line $L$ intersects with $O(\log n)$ triangles.

I divide $P$ in half using a diagonal line. Then I continue in each half in the same way. But at this step I get stuck.

Let the polygon be defined by the vertices in clockwise order: $(v_1, \dotsc, v_n)$. For simplicity, assume that $n$ is even.

• Add the lines: $(v_1,v_3)$, $(v_3,v_5)$,...,$(v_{n-2},v_1)$.

• Then, recursively triangulate the polygon: $(v_1, v_3, \dotsc, v_{n-2})$.

Note that, the algorithm creates $n/2$ triangles in step $1$. And, any arbitrary line $L$ can intersect at most $2$ of these triangles. By induction, it is easy to prove that any line $L$ will not intersect more than $2 \log n$ triangles overall.

StackExchange Computer Science Q#148888, answer score: 3