July 5, 1998.

These are quick hacks (which always take longer than one expects) that illustrate that the algorithm for minimum convex decomposition of Keil and Snoeyink (CCCG 98) can actually be implemented in O(n r^2) time and space.

MCD Minimum convex decomposition of a simple polygon MWT Minimum weight triangulation of a simple polygon VPTest Visibility algorithm tester

CompGeom/ geometry classes

These can run as standalone (e.g. java MCD) or as applets from the .html files.

If you find this useful, please let us know. Mark keil@cs.usask.ca Jack snoeyink@cs.ubc.ca

http://www.cs.ubc.ca/~snoeyink/demos/convdecomp/MCDDemo.html