OREGON STATE UNIVERSITY

You are here

Near-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets

TitleNear-Linear-Time Deterministic Plane Steiner Spanners and TSP Approximation for Well-Spaced Point Sets
Publication TypeConference Paper
Year of Publication2012
AuthorsBorradaile, G., and D. Eppstein
Conference NameCoRR
Date Published08/2012
Conference LocationCharlottetown, Prince Edward Island, Canada
Abstract

We describe an algorithm that takes as input n points in the plane and a parameter {\epsilon}, 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 + {\epsilon})-approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has bounded sharpest angle, our algorithm's output has O(n) vertices, its weight is O(1) times the minimum spanning tree weight, and the algorithm's running time is bounded by O(n \sqrt{log log n}). We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem.