Near-linear-time deterministic plane Steiner spanners forwell-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.
spanner sparse euclidean tsp