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

  • 1
    $\begingroup$ Do you have a question? $\endgroup$ – 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.

Chazelle proposed a linear time algorithm, but i don't know whether the algorithm has ever been implemented, since it is very complex.

You may also consult the wikipedia page.

A more in-depth reference is Berg's Computational Geometry


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.