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

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

Semi-automatically filtered from a common source file.