A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
Glencora Borradaile, Philip N. Klein, Claire Mathieu · 2008
We give a randomized O(n2log n)-time approximation scheme for the Steiner forest problem in the Euclidean plane. For every fixed epsi > 0 and given any n pairs of terminals in the plane, our scheme finds a (1 + epsi)- approximation to the minimum-length forest that connects every pair of terminals.