Approximating the minimum weight Steiner triangulation

David Eppstein
Discrete & Computational Geometry 11(2):163–191, 1994
Proc. 3rd Symp. Discrete Algorithms, ACM and SIAM, Jan 1992, pp. 48–57
Tech. report 91-55, Univ. of California, Irvine, Dept. of Information and Computer Science, 1991
Mathematical Reviews 95e:68218
Mathematical Reviews 93e:68099
http://www.ics.uci.edu/~eppstein/pubs/Epp-TR-91-55.pdf

Cited by:

• Refining a triangulation of a planar straight-line graph to eliminate large angles
• Computing a subgraph of the minimum weight triangulation
• Approximation algorithms for geometric tour and network design problems
• A fast heuristic for approximating the minimum weight triangulation
• Average-case ray shooting and minimum weight triangulations
• Triangulations
• Progress in Hierarchical Clustering & Minimum Weight Triangulation
• A large subgraph of the minimum weight triangulation
• Quasi-greedy triangulations approximating the minimum weight triangulation
• Approximate minimum weight Steiner triangulation in three dimensions
• Approximating minimum-weight triangulations in three dimensions
• Navigating through triangle meshes implemented as linear quadtrees
• Quadtree decomposition, Steiner triangulation, and ray shooting
• Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability
• Optimal triangulations
• Computational geometry column 42
• Polygon decomposition for efficient construction of Minkowski sums
• Robust and Efficient Construction of Planar Minkowski Sums
• Quadtree, ray shooting and approximate minimum weight Steiner triangulation
• NP-completeness column 24