On Steiner tree problem with 45° routing
D.T. Lee, Chin-Fang Shen, Chenwen Ding · 2002
We consider Steiner minimal trees (SMT) in the plane where the orientations of interconnection are restricted to be either horizontal, vertical or of slopes +1 and -1. We derive a ratio, 1/4-2/spl radic/2 which we conjecture to be the Steiner ratio for 45/spl deg/-SMT. We provide a method to find an optimal 45/spl deg/-SMT for 3 or 4 points by analyzing its topological connections. For arbitrary point set of size n we present an O(n log n) time heuristic based on the notions of 45/spl deg/ minimum spanning tree and Delaunay triangulation. Empirical results compared with the rectilinear and Euclinear cases are given.