On Steiner Minimal Trees with Rectilinear Distance

1976/01/01 by F. K. Hwang · 5 citations
Engineering · Computer Science · Mathematics · #VLSI and FPGA Design Techniques #Interconnection Networks and Systems #Computational Geometry and Mesh Generation #Combinatorics #Steiner tree problem #Mathematics #Tree (set theory) #Plane (geometry) #Cartesian coordinate system #Spanning tree #Discrete mathematics #Geometry

paper · doi:10.1137/0130013

openalex publication_date 1976/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30

Abstract

We consider Steiner minimal trees in the plane with rectilinear distance. The rectilinear distance d(p₁ ,p₂ ) between two points p₁ , p₂ is | x₁ - x₂ | + | y₁ - y₂ |, where the (x_i ,y_i ) are the Cartesian coordinates of the p_i . For a given finite set P of points, let l_s denote the length of a Steiner minimal tree and l_m the length of a minimal spanning tree. The main result of the memorandum is that l_s / l_m \geqq (2)/(3).

Citations

• On the shortest spanning subtree of a graph and the traveling salesman problem

Cited by

• A NEW BOUND FOR EUCLIDEAN STEINER MINIMAL TREES
• Branched coverings and Steiner ratio
• Dynamic Programming for Minimum Steiner Trees
• The Rectilinear Steiner Tree Problem is NP-Complete
• Steiner tree problem [wikipedia]