Abstract.
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 compute requiring only O(n 2 ) time and O(n) space in the expected case for uniform distributions. Several experimental implementations of both approaches have shown that for moderate-sized point sets (up to 350 points^1) the skeletons are connected, enabling an efficient completion of the exact MWT. We are thus able to compute the MWT of substantially larger random point sets than have previously been computed.
^1Though in this paper we summarize some empirical findings for input sets of up to 350 points, a variant of the algorithm has been implemented and tested on up to 40,000 points producing connected subgraphs [2].
Article PDF
Similar content being viewed by others
Author information
Authors and Affiliations
Additional information
Received May 29, 1996, and in revised form January 10, 1997.
Rights and permissions
About this article
Cite this article
Dickerson, M., Keil, J. & Montague, M. A Large Subgraph of the Minimum Weight Triangulation . Discrete Comput Geom 18, 289–304 (1997). https://doi.org/10.1007/PL00009320
Issue Date:
DOI: https://doi.org/10.1007/PL00009320