Implementations of the LMT heuristic for minimum weight triangulation
Ronald Beirouti, Jack Scott Snoeyink · 1998
No polynomial-time algorithm is kno-ivn to compute t,he minimum weight triangulation (MWT) of a finite planar point set.In this paper xve present efficient implementat,ions of the LMT-skeleton heurist'ic, xvhich identifies edges that must be, and cannot be, in an MWT.For uniformly distributed points, v:e can compute the esact MWT of tens of thousands of points in minutes.These results are obtained by improving the asymptot,ic time and memory usage of the LMTskeleton heurist.ic and of filters that identify initial candidate edges, and also by bucketing and further t,uning for evenly distributed points.Further details and an implementation as a macro for the IPE dran;ng prog7cam are available on the web: http://www.cs.ubc.ca/spider/snoeyink/mwt.