Approximate Euclidean Steiner Trees

Charl Ras (), Konrad Swanepoel () and Doreen Anne Thomas ()
Additional contact information
Charl Ras: University of Melbourne
Konrad Swanepoel: London School of Economics and Political Science
Doreen Anne Thomas: University of Melbourne

Journal of Optimization Theory and Applications, 2017, vol. 172, issue 3, No 7, 845-873

Abstract: 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^{\circ }$$ 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-dimensional case we derive a lower bound for the relative error in length. This bound is linear in terms of the maximum angle error when the angle error is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error in length for larger values of the maximum angle error and calculate exact values in the plane for three and four terminals.

Keywords: Approximate Steiner tree; Euclidean Steiner problem; Shortest networks; Approximation; 90C35; 05C05; 90B10 (search for similar items in EconPapers)
Date: 2017
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-016-1036-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:172:y:2017:i:3:d:10.1007_s10957-016-1036-5

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-016-1036-5

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().