**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.

(BibTeX -- Citations -- CiteSeer)

Publications -- David Eppstein -- Theory Group -- Inf. & Comp. Sci. -- UC Irvine

Semi-automatically filtered from a common source file.