Approximate Euclidean Steiner trees
From MaRDI portal
Publication:2397467
DOI10.1007/S10957-016-1036-5zbMATH Open1362.90354arXiv1605.01172OpenAlexW3099580205WikidataQ59521383 ScholiaQ59521383MaRDI QIDQ2397467FDOQ2397467
D. A. Thomas, Konrad J. Swanepoel, C. J. Ras
Publication date: 22 May 2017
Published in: Journal of Optimization Theory and Applications (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1605.01172
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
Programming involving graphs or networks (90C35) Trees (05C05) Deterministic network models in operations research (90B10)
Cites Work
- The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study
- Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
- The Steiner tree problem
- Upper and lower bounds for the lengths of Steiner trees in 3-space
- Steiner Minimal Trees
- Approximating minimum Steiner point trees in Minkowski planes
- On the Problem of Steiner
- The Complexity of Computing Steiner Minimal Trees
- Guillotine Subdivisions Approximate Polygonal Subdivisions: A Simple Polynomial-Time Approximation Scheme for Geometric TSP, k-MST, and Related Problems
- Title not available (Why is that?)
- Geometric methods and optimization problems
- How to find Steiner minimal trees in Euclidean \(d\)-space
- Geometric conditions for Euclidean Steiner trees in \(\mathbb R^d\)
- Title not available (Why is that?)
- Steiner minimal trees
- A novel approach to phylogenetic trees: d‐Dimensional geometric Steiner trees
- Title not available (Why is that?)
- Dealing with large hidden constants
- Title not available (Why is that?)
- Complex Numbers from A to ... Z
- Optimal interconnection trees in the plane. Theory, algorithms and applications
- Title not available (Why is that?)
- A linear time algorithm for full Steiner trees
- On the history of the Euclidean Steiner tree problem
- Minimum networks for four points in space
- Approximations and lower bounds for the length of minimal Euclidean Steiner trees
- Analytic formulas for full Steiner trees
- An example of an infinite Steiner tree connecting an uncountable set
- When Hamming Meets Euclid: The Approximability of Geometric TSP and Steiner Tree
- Euclidean Steiner minimal trees, minimum energy configurations, and the embedding problem of weighted graphs in \(E^ 3\)
Cited In (6)
- Euclidean TSP in narrow strips
- A Polynomial-Time Approximation Scheme for Euclidean Steiner Forest
- Title not available (Why is that?)
- 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
Uses Software
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)
