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(kn²) time, which is possibly as bad as O(n³) time.

Instructions for Using the Applet

• A simple polygon must be inputted.
• Click the left mouse button to input a point.
• Click the middle or right mouse button after you have inputted your last point. The edge from the first point to the last point will be added automatically.

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