1
$\begingroup$

enter image description here

The book says triangulation algorithm takes quadratic time in worst case. but why? The book says - take leftmost vertex and try to connect its neighbors. If you succeed - you get triangle and polygon enter image description here

and therefore as the consequence you get quadratic time algo. But why? I made this procedure and for a polygon of 7 vertices I performed 4 divisions... enter image description here

In general I do not see how quadratic time is possible... cannot come up with an instance.

$\endgroup$
1
  • 1
    $\begingroup$ Trying to get an idea about the complexity of something by doing by hand the case n=7 has very little chance of being useful. $\endgroup$ Feb 13 '18 at 2:30
3
$\begingroup$

Your diagrams are of convex polygons. The algorithm is for a polygon which may be decidedly concave, with hundreds of edges crossing the $uw$ line.

$\endgroup$
1

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.