Near-linear-time deterministic plane Steiner spanners for well-spaced point sets

We describe an algorithm that takes as input n points in the plane and a parameter ϵ  , and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a (1+ϵ)(1+ϵ)-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has sharpest angle α  , our algorithm's output has O(β2ϵn) vertices, its weight is O(βα) times the minimum spanning tree weight where β=1αϵlog⁡1αϵ. The algorithm's running time, if a Delaunay triangulation is given, is linear in the size of the output. We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.