- Approximating the minimum weight Steiner triangulation.
D. Eppstein.
Tech. Rep. 91-55, ICS, UCI, 1991.
3rd ACM-SIAM Symp. Discrete Algorithms, Orlando, 1992, pp. 48–57.
Disc. Comp. Geom. 11: 163–191, 1994.Quadtree based triangulation gives a large but constant factor approximation to the minimum weight triangulation of a point set or convex polygon, allowing extra Steiner points to be added as vertices. Includes proofs of several bounds on triangulation weight relative to the minimum spanning tree or non-Steiner triangulation, and a conjecture that for convex polygons the only points that need to be added are on the polygon boundary.