A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets

DOI10.1007/BF01758761zbMath0748.68030MaRDI QIDQ1186799

D. S. Richards, Jeffrey S. Salowe

Publication date: 28 June 1992

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

Steiner minimal treerectilinear metricrectangular convex hull

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Dynamic programming (90C39)

Related Items

The Steiner tree problem in orientation metrics ⋮ Unnamed Item ⋮ The Steiner tree problem for terminals on the boundary of a rectilinear polygon ⋮ Steiner's problem in double trees ⋮ Planar Manhattan local minimal and critical networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the X-Y convex hull of a set of X-Y polygons
• Algorithms for special cases of rectilinear steiner trees: I. Points on the boundary of a rectilinear rectangle
• Convexity and the Steiner tree problem
• On Steiner Minimal Trees with Rectilinear Distance
• Rectilinear steiner trees: Efficient special-case algorithms
• Faster exact algorithms for steiner trees in planar networks
• On Steiner’s Problem with Rectilinear Distance