Approximate Euclidean Steiner Trees

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 from 120 ∘. This notion arises in numerical approximations of minimum Steiner trees. We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology. It has been conjectured that this relative error is at most linear in the maximum error at the angles, independent of the number of terminals. We verify this conjecture for the two-dimensional case as long as the maximum angle error is sufficiently small in terms of the number of terminals. In the two-dim..