- View PDF version of TR-97-11 (445097 bytes)
- View PostScript version of TR-97-11
- Save PostScript version of TR-97-11
- Save gzipped PostScript version of TR-97-11 (188787 bytes)

- A Fast Heuristic For Finding The Minimum Weight Triangulation, July 10, 1997 Ronald Beirouti
No polynomial time algorithm is known to compute the minimum weight triangulation MWT of a point set. In this thesis we present an efficient implementation of the LMT-skeleton heuristic. This heuristic computes a subgraph of the MWT of a point set from which the MWT can usually be completed. For uniformly distributed sets of tens of thousands of points our algorithm constructs the exact MWT in expected linear time and space. A fast heuristic, other than being usefull in areas such as stock cutting, finite element analysis, and terrain modeling, allows to experiment with different point sets in order to explore the complexity of the MWT problem. We present point sets constructed with this implementation such that the LMT-skeleton heuristic does not produce a complete graph and can not compute the MWT in polynomial time, or that can be used to prove the NP-Hardness of the MWT problem.

If you have any questions or comments regarding this page please send mail to help@cs.ubc.ca.