Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm

Martin Zachariasen, Pawel Winter

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

27 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAlgorithm Engineering and Experimentation
Subtitle of host publicationInternational Workshop ALENEX'99 Baltimore, MD, USA, January 15--16, 1999 Selected Papers
EditorsMichael T. Goodrich, Catherine C. McGeoch
Place of PublicationBerlin, Heidelberg
PublisherSpringer Berlin Heidelberg
Number of pages14
ISBN (Print)3-540-66227-8
Publication statusPublished - 1999

Publication series

NameLecture Notes in Computer Science (LNCS, volume 1619)


  • minimum span tree
  • steiner tree
  • exact algorithm
  • steiner point
  • steiner tree problem


Dive into the research topics of 'Obstacle-Avoiding Euclidean Steiner Trees in the Plane: An Exact Algorithm'. Together they form a unique fingerprint.

Cite this