$(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.