Steiner trees for fixed orientation metrics

Marcus Brazil, Martin Zachariasen

Research output: Contribution to journalArticlepeer-review

11 Citations (Scopus)


We consider the problem of constructing Steiner minimum trees for a metric defined by a polygonal unit circle (corresponding to σ ≥ 2 weighted legal orientations in the plane). A linear-time algorithm to enumerate all angle configurations for degree three Steiner points is given. We provide a simple proof that the angle configuration for a Steiner point extends to all Steiner points in a full Steiner minimum tree, such that at most six orientations suffice for edges in a full Steiner minimum tree. We show that the concept of canonical forms originally introduced for the uniform orientation metric generalises to the fixed orientation metric. Finally, we give an O(σ n) time algorithm to compute a Steiner minimum tree for a given full Steiner topology with n terminal leaves.
Original languageEnglish
Pages (from-to)141-169
Number of pages29
JournalJournal of Global Optimization
Issue number1
Publication statusPublished - 2009


  • steiner tree problem
  • normed plane
  • fixed orientation metric
  • canonical form
  • fixed topology


Dive into the research topics of 'Steiner trees for fixed orientation metrics'. Together they form a unique fingerprint.

Cite this