The rectilinear Steiner ratio

  • PO de Wet Department of Decision Sciences, University of South Africa, PO Box 392, Pretoria, 0003, South Africa,
Keywords: Steiner ratio, Steiner tree, spanning tree, rectilinear tree, L<sub>1</sub> norm, NP-complete

Abstract

The rectilinear Steiner ratio was shown to be 3/2 by Hwang [Hwang FK, 1976, On Steiner minimal trees with rectilinear distance, SIAM Journal on Applied Mathematics, 30, pp. 104–114.]. We use continuity and introduce restricted point sets to obtain an alternative, short and self-contained proof of this result.
Key words: Steiner ratio, Steiner tree, spanning tree, rectilinear tree, L1 norm, NP-complete.
ORiON Vol.21(1) 2005: 53-61
Published
2005-06-17
Section
Articles

Journal Identifiers


eISSN: 0529-191-X