O(n) Time Algorithm

Contents

One-Mouth Theorem


Interactive Ear Cutting!


Introduction to the Applet

This applet uses the O(kn) time algorithm to cut ears from a simple polygon. It is interesting to note that by using this algorithm to cut ears from the simple polygon until no more ears can be cut, the polygon is triangulated in O(kn2) time, which is possibly as bad as O(n3) time.

Instructions for Using the Applet





If you wish, you can see the source code. Classes written by Steve Robbins were also used. They are available on his homepage.



O(n) Time Algorithm

Contents

One-Mouth Theorem



This page was last updated on Wednesday, December 10th, 1997.

© 1997 Ian Inc.