1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Do you have a question? $\endgroup$
    – abiessu
    Dec 11, 2016 at 23:12

1 Answer 1

2
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .