Lower bounds for rectilinear Steiner trees in bounded space

DOI10.1016/0020-0190(91)90136-6zbMath0713.68098OpenAlexW2484843909MaRDI QIDQ750175

Timothy Law Snyder

Publication date: 1991

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90136-6

zbMATH Keywords

combinatorial problemslower boundscomputational geometryrectilinear Steiner treeworst-case

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Minimum rectilinear Steiner tree of \(n\) points in the unit square, Worst-case minimum rectilinear Steiner trees in all dimensions, A note on lower bounds for rectilinear Steiner trees

Cites Work

• Two probabilistic results on rectilinear Steiner trees
• On Steiner trees for bounded point sets
• The Travelling Salesman Problem and Minimum Matching in the Unit Square
• On the Exact Location of Steiner Points in General Dimension
• On Steiner Minimal Trees with Rectilinear Distance
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The largest minimal rectilinear steiner trees for a set of n points enclosed in a rectangle with given perimeter
• On Steiner’s Problem with Rectilinear Distance
• Steiner Minimal Trees