Approximate Euclidean Steiner trees

DOI10.1007/S10957-016-1036-5MaRDI QIDQ2397467zbMATH OpenOpenAlexWikidataFDO

Authors D. A. Thomas, C. J. Ras, Konrad J. Swanepoel

Publication date 22 May 2017

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1605.01172

zbMATH Keywords

approximationEuclidean Steiner problemshortest networksapproximate Steiner tree

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Deterministic network models in operations research (90B10)

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 $e$, independent of the number of terminals. We verify their conjecture for the two-dimensional case as long as the error $e$ is sufficiently small in terms of the number of terminals. We derive a lower bound linear in $e$ for the relative error in the two-dimensional case when $e$ is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error for larger values of $e$, and calculate exact values in the plane for three and four terminals.

Recommendations

• Approximations and lower bounds for the length of minimal Euclidean Steiner trees
• scientific article; zbMATH DE number 3912403
• Approximations for Steiner trees with minimum number of Steiner points
• Steiner Trees for Terminals Constrained to Curves
• Approximating minimum Steiner point trees in Minkowski planes

Cites work

• scientific article; zbMATH DE number 5282830 (Why is no real title available?)
• scientific article; zbMATH DE number 700023 (Why is no real title available?)
• scientific article; zbMATH DE number 1775442 (Why is no real title available?)
• scientific article; zbMATH DE number 195007 (Why is no real title available?)
• scientific article; zbMATH DE number 970831 (Why is no real title available?)
• A linear time algorithm for full Steiner trees
• A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
• An example of an infinite Steiner tree connecting an uncountable set
• Analytic formulas for full Steiner trees
• Approximating minimum Steiner point trees in Minkowski planes
• Approximations and lower bounds for the length of minimal Euclidean Steiner trees
• Complex numbers from A to \dots Z
• Dealing with large hidden constants, engineering a planar Steiner tree PTAS
• Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in E^ 3
• Geometric conditions for Euclidean Steiner trees in R^d
• Geometric methods and optimization problems
• Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
• How to find Steiner minimal trees in Euclidean \(d\)-space
• Minimum networks for four points in space
• On the Problem of Steiner
• On the history of the Euclidean Steiner tree problem
• Optimal interconnection trees in the plane. Theory, algorithms and applications
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Steiner Minimal Trees
• Steiner minimal trees
• The Complexity of Computing Steiner Minimal Trees
• The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
• The Steiner tree problem
• Upper and lower bounds for the lengths of Steiner trees in 3-space
• When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree

Cited in

(6)

• Euclidean TSP in narrow strips
• A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
• scientific article; zbMATH DE number 7053371 (Why is no real title available?)
• Euclidean Steiner trees optimal with respect to swapping 4-point subtrees
• Light Euclidean Spanners with Steiner Points
• Approximations and lower bounds for the length of minimal Euclidean Steiner trees

Describes a project that uses

Uses Software

• DIMACS
• GeoSteiner

This page was built for publication: Approximate Euclidean Steiner trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397467)