Approximate Euclidean Steiner Trees
arXiv:1605.01172 · doi:10.1007/s10957-016-1036-5
Abstract
An approximate Steiner tree is a Steiner tree on a given set of terminals in Euclidean space such that the angles at the Steiner points are within a specified error e from 120 degrees.This notion arises in numerical approximations of minimum Steiner trees (W. D. Smith, Algorithmica, 7 (1992), 137--177). We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology.Rubinstein, Weng and Wormald (J. Global Optim. 35 (2006), 573--592) conjectured that this relative error is at most linear in , independent of the number of terminals. We verify their conjecture for the two-dimensional case as long as the error is sufficiently small in terms of the number of terminals. We derive a lower bound linear in for the relative error in the two-dimensional case when is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error for larger values of , and calculate exact values in the plane for three and four terminals.
24 pages, 9 figures