# Finding a diagonal that lies entirely in the interior of the polygon

$(X_1,Y_1),(X_2,Y_2),...,(X_n,Y_n)$ are $n$ ordered points in the Cartesian plane that are successive vertices of a non-intersecting closed polygon.

Describe how to find efficiently a diagonal (that is, a line joining 2 vertices) that lies entirely in the interior of the polygon.

Repeated application of this process will completely triangulate the interior of the polygon. Estimate the worst case number of arithmetic operations needed to complete the triangulation.

• Do you have a question? – abiessu Dec 11 '16 at 23:12

If you only need one diagonal, then ear clipping is a method which finds a diagonal in $O(n)$. But repeated application of this method is not good for triangulating the whole polygon since it runs in $O(n^2)$
A better method for triangulating a polygon is using monotone polygon decomposition, called GJPT-78 (Garey-Johnson-Preparata-Tarjan, 1978) which runs in $O(n\log n)$. This is the algorithm which I used for my projects.