Minimum rectilinear Steiner tree of n points in the unit square

DOI10.1016/J.COMGEO.2017.06.007MaRDI QIDQ1699296zbMATH OpenOpenAlexFDO

Authors Adrian Dumitrescu, Minghui Jiang

Publication date 19 February 2018

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2017.06.007

zbMATH Keywords

coveringpackinginteger partitionminimum rectilinear Steiner tree

Mathematics Subject Classification ID

Trees (05C05)

Recommendations

• Minimal Steiner trees for rectangular arrays of lattice points
• scientific article; zbMATH DE number 4041289
• A rectilinear steiner minimal tree algorithm for convex point sets
• Approximations for Steiner trees with minimum number of Steiner points
• Approximations for Steiner trees with minimum number of Steiner points
• A linear-time algorithm to construct a rectilinear Steiner minimal tree for \(k\)-extremal point sets
• Approximating minimum Steiner point trees in Minkowski planes
• Worst-case minimum rectilinear Steiner trees in all dimensions
• scientific article; zbMATH DE number 8006
• Minimizing path lengths in rectilinear Steiner minimum trees with fixed topology

Cites work

• scientific article; zbMATH DE number 3735154 (Why is no real title available?)
• scientific article; zbMATH DE number 3588048 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A course in combinatorics.
• Fast heuristic algorithms for rectilinear Steiner trees
• Geometric Spanner Networks
• How Long Can a Euclidean Traveling Salesman Tour Be?
• Lower bounds for rectilinear Steiner trees in bounded space
• On Steiner Minimal Trees with Rectilinear Distance
• On Steiner trees for bounded point sets
• On Steiner’s Problem with Rectilinear Distance
• On the Shortest Path Through a Number of Points
• Rectilinear Steiner tree heuristics and minimum spanning tree algorithms using geographic nearest neighbors
• Steiner Minimal Trees
• The Complexity of Computing Steiner Minimal Trees
• 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
• The shortest path and the shortest road through n points
• Worst-case minimum rectilinear Steiner trees in all dimensions
• Worst-case ratios of networks in the rectilinear plane
• Über einen geometrischen Satz

Cited in

(5)

• scientific article; zbMATH DE number 1512092 (Why is no real title available?)
• scientific article; zbMATH DE number 1099658 (Why is no real title available?)
• On the stretch factor of polygonal chains
• Minimal Steiner trees for rectangular arrays of lattice points
• scientific article; zbMATH DE number 7561700 (Why is no real title available?)

This page was built for publication: Minimum rectilinear Steiner tree of \(n\) points in the unit square

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1699296)