Abstract
The first exact algorithm for the obstacle-avoiding Euclidean Steiner tree problem in the plane (in its most general form) is presented. The algorithm uses a two-phase framework — based on the generation and concatenation of full Steiner trees — previously shown to be very successful for the obstacle-free case. Computational results for moderate size problem instances are given; instances with up to 150 terminals have been solved to optimality within a few hours of CPU-time.
Supported partially by the Danish Natural Science Research Council under contract 9701414 (project “Experimental Algorithmics”).
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
Preview
Unable to display preview. Download preview PDF.
References
A. Armillotta and G. Mummolo. A Heuristic Algorithm for the Steiner Problem with Obstacles. Technical report, Dipt. di Pregettazione e Produzione Industriale, Univ. degli Studi di Bari, Bari, 1988.
F. K. Hwang, D. S. Richards, and P. Winter. The Steiner Tree Problem. Annals of Discrete Mathematics 53. Elsevier Science Publishers, Netherlands, 1992.
K. Mehlhorn and S. Näher. LEDA-A Platform for Combinatorial and Geometric Computing. Max-Planck-Institut für Informatik, Saarbrücken, Germany, http://www.mpi-sb.mpg.de/LEDA/leda.html, 1996.
J. S. Provan. An Approximation Scheme for Finding Steiner Trees with Obstacles. SIAM Journal on Computing, 17(5):920–934, 1988.
J. M. Smith, D. T. Lee, and J. S. Liebman. An O(n log n) Heuristic for Steiner Minimal Tree Problems on the Euclidean Metric. Networks, 11:23–29, 1981.
D. M. Warme. Spanning Trees in Hypergraphs with Applications to Steiner Trees. Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.
D. M. Warme, P. Winter, and M. Zachariasen. Exact Algorithms for Plane Steiner Tree Problems: A Computational Study. In D.-Z. Du, J. M. Smith, and J. H. Rubinstein, editors, Advances in Steiner Trees, Kluwer Academic Publishers, Boston, to appear.
E. Welzl. Constructing the Visibility Graph for n-line Segments in O(n 2) Time. Information Processing Letters, 20:167–171, 1985.
P. Winter. An Algorithm for the Steiner Problem in the Euclidean Plane. Networks, 15:323–345, 1985.
P. Winter. Euclidean Steiner Minimal Trees with Obstacles and Steiner Visibility Graphs. Discrete Applied Mathematics, 47:187–206, 1993.
P. Winter and J. M. Smith. Steiner Minimal Trees for Three Points with One Convex Polygonal Obstacle. Annals of Operations Research, 33:577–599, 1991.
P. Winter and M. Zachariasen. Euclidean Steiner Minimum Trees: An Improved Exact Algorithm. Networks, 30:149–166, 1997.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Zachariasen, M., Winter, P. (1999). Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm. In: Goodrich, M.T., McGeoch, C.C. (eds) Algorithm Engineering and Experimentation. ALENEX 1999. Lecture Notes in Computer Science, vol 1619. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48518-X_17
Download citation
DOI: https://doi.org/10.1007/3-540-48518-X_17
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-66227-3
Online ISBN: 978-3-540-48518-6
eBook Packages: Springer Book Archive