A LARGE SUBGRAPH OF THE MINIMUM WEIGHT TRIANGULATION

We present an O(n(4))-time and O(n(2))-space algorithm that computes a subgraph of the minimum weight triangulation (MWT) of a general point set. The algorithm works by finding a collection of edges guaranteed to be in any locally minimal triangulation. We call this subgraph the LMT-skeleton. We also give a variant called the modified LMT-skeleton that is both a more complete subgraph of the MWT and is faster to comp ute requiring only O(n(2)) time and O(n) space in the expected case fd r uniform distributions. Several experimental implementations of both approaches have shown that for moderate-sized point sets (up to 350 po ints') the skeletons are connected, enabling an efficient completion o f the exact MWT. We are thus able to compute the MWT of substantially larger random point sets than have previously been computed.