×

Approximations and lower bounds for the length of minimal Euclidean Steiner trees. (English) Zbl 1133.90408

Summary: We give a new lower bound on the length of the minimal Steiner tree with a given topology joining given terminals in Euclidean space, in terms of toroidal images. The lower bound is equal to the length when the topology is full. We use the lower bound to prove bounds on the “error” \(e\) in the length of an approximate Steiner tree, in terms of the maximum deviation \(d\) of an interior angle of the tree from \(120^\circ\). Such bounds are useful for validating algorithms computing minimal Steiner trees. In addition we give a number of examples illustrating features of the relationship between \(e\) and \(d\), and make a conjecture which, if true, would somewhat strengthen our bounds on the error.

MSC:

90C35 Programming involving graphs or networks
52B12 Special polytopes (linear programming, centrally symmetric, etc.)
54F50 Topological spaces of dimension \(\leq 1\); curves, dendrites
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Arora, S. (1996), Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of the 37th Annual Symposium on Foundations of Computer Sciences, pp. 2–13.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.