Abstract
Some of the most efficient heuristics for the Euclidean Steiner minimal tree problem in the d-dimensional space, \(d \ge 2\), use Delaunay tessellations and minimum spanning trees to determine small subsets of geometrically close terminals. Their low-cost Steiner trees are determined and concatenated in a greedy fashion to obtain a low cost tree spanning all terminals. The weakness of this approach is that obtained solutions are topologically related to minimum spanning trees. To avoid this and to obtain even better solutions, bottleneck distances are utilized to determine good subsets of terminals without being constrained by the topologies of minimum spanning trees. Computational experiments show a significant solution quality improvement.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bajaj, C.: The algebraic degree of geometric optimization problems. Discrete Comput. Geom. 3, 177–191 (1988)
Beasley, J.E., Goffinet, F.: A Delaunay triangulation-based heuristic for the Euclidean Steiner problem. Networks 24(4), 215–224 (1994)
de Berg, M., Cheong, O., van Krevald, M., Overmars, M.: Computational Geometry - Algorithms and Applications, 3rd edn. Springer, Heidelberg (2008)
Brazil, M., Graham, R.L., Thomas, D.A., Zachariasen, M.: On the history of the Euclidean Steiner tree problem. Arch. Hist. Exact Sci. 68, 327–354 (2014)
Brazil, M., Zachariasen, M.: Optimal Interconnection Trees in the Plane. Springer, Cham (2015)
DIMACS, ICERM: 11th DIMACS Implementation Challenge: Steiner Tree Problems (2014). http://dimacs11.cs.princeton.edu/
Fampa, M., Anstreicher, K.M.: An improved algorithm for computing Steiner minimal trees in Euclidean d-space. Discrete Optim. 5, 530–540 (2008)
Fampa, M., Lee, J., Maculan, N.: An overview of exact algorithms for the Euclidean Steiner tree problem in n-space, Int. Trans. OR (2015)
Fonseca, R., Brazil, M., Winter, P., Zachariasen, M.: Faster exact algorithms for computing Steiner trees in higher dimensional Euclidean spaces. In: Proceedings of the 11th DIMACS Implementation Challenge, Providence, Rhode Island, USA (2014). http://dimacs11.cs.princeton.edu/workshop.html
do Forte, V.L., Montenegro, F.M.T., de Moura Brito, J.A., Maculan, N.: Iterated local search algorithms for the Euclidean Steiner tree problem in \(n\) dimensions. Int. Trans. OR (2015)
Gilbert, E.N., Pollak, H.O.: Steiner minimal trees. SIAM J. Appl. Math. 16(1), 1–29 (1968)
Hwang, F.K., Richards, D.S., Winter, P.: The Steiner Tree Problem. North-Holland, Amsterdam (1992)
Juhl, D., Warme, D.M., Winter, P., Zachariasen, M.: The GeoSteiner software package for computing Steiner trees in the plane: an updated computational study. In: Proceedings of the 11th DIMACS Implementation Challenge, Providence, Rhode Island, USA (2014). http://dimacs11.cs.princeton.edu/workshop.html
Laarhoven, J.W.V., Anstreicher, K.M.: Geometric conditions for Euclidean Steiner trees in \({R}^d\). Comput. Geom. Theor. Appl. 46(5), 520–531 (2013)
Laarhoven, J.W.V., Ohlmann, J.W.: A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in \({R}^d\). J. Heuristics 17(4), 353–372 (2011)
Lorenzen, S.S., Winter, P.: Code and Data Repository at Github (2016). https://github.com/StephanLorenzen/ESMT-heuristic-using-bottleneck-distances/blob/master/README.md
Olsen, A., Lorenzen, S. Fonseca, R., Winter, P.: Steiner tree heuristics in Euclidean \(d\)-space. In: Proceedings of the 11th DIMACS Implementation Challenge, Providence, Rhode Island, USA (2014). http://dimacs11.cs.princeton.edu/workshop.html
Seidel, R.: The upper bound theorem for polytopes: an easy proof of its asymptotic version. Comp. Geom.-Theor. Appl. 5, 115–116 (1995)
Sleator, D.D., Tarjan, R.E.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362–391 (1983)
Smith, J.M., Lee, D.T., Liebman, J.S.: An O(\(n \log n\)) heuristic for Steiner minimal tree problems on the Euclidean metric. Networks 11(1), 23–39 (1981)
Smith, W.D.: How to find Steiner minimal trees in Euclidean d-space. Algorithmica 7, 137–177 (1992)
Toppur, B., Smith, J.M.: A sausage heuristic for Steiner minimal trees in three-dimensional Euclidean space. J. Math. Model. Algorithms 4, 199–217 (2005)
Warme, D.M., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: a computational study. In: Du, D.-Z., Smith, J., Rubinstein, J. (eds.) Advances in Steiner Trees, pp. 81–116. Springer, Dordrecht (2000)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer International Publishing Switzerland
About this paper
Cite this paper
Lorenzen, S.S., Winter, P. (2016). Steiner Tree Heuristic in the Euclidean d-Space Using Bottleneck Distances. In: Goldberg, A., Kulikov, A. (eds) Experimental Algorithms. SEA 2016. Lecture Notes in Computer Science(), vol 9685. Springer, Cham. https://doi.org/10.1007/978-3-319-38851-9_15
Download citation
DOI: https://doi.org/10.1007/978-3-319-38851-9_15
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-38850-2
Online ISBN: 978-3-319-38851-9
eBook Packages: Computer ScienceComputer Science (R0)