Approximating geometrical graphs via “spanners” and “banyans”

Abstract

probability l/2 in a Monte Carlo sense2 in time The main result of t,his paper is an improvement of Arora's method to find (l+e) approximations for geometric NP-hard problems including the Euclidean Traveling Salesman Problem and t.he Euclidean Steiner Minimum Tree problems. For f&d dimension d and E, our algorithms run in O(NlogN) time. (s\/;i) O(d(+.&)d-') N + O(dN log N)