# 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.

• I'm not sure if your approach is the best way. Maybe a better idea is to ignore the triangles for a moment, and think about how the structure would look like if the line can only intersect $O(\log n)$ triangles or edges. Since we need it to be small independent of the direction, it seems you should make concentric "rings" with the same shape as the convex polygon, which decrease in size until the central ring is a triangle. To show that this structure has a "depth" of $O(\log n)$, look at the dual of the triangulation. Feb 2, 2022 at 16:56
Let the polygon be defined by the vertices in clockwise order: $$(v_1, \dotsc, v_n)$$. For simplicity, assume that $$n$$ is even.
1. Add the lines: $$(v_1,v_3)$$, $$(v_3,v_5)$$,...,$$(v_{n-2},v_1)$$.
2. 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.