ON RECTILINEAR DISTANCE-PRESERVING TREES (REPRINTED)

Given a set of terminals on the plane N={s, v(1),...,v(n)}, with a sou rce terminal s, a Rectilinear Distance-Preserving Tree (RDPT) T(V, E) is defined as a tree rooted at s, connecting all terminals in N. An RD PT has the property that the length of every source to sink path is eq ual to the rectilinear distance between that source and sink. A Min-Co st Rectilinear Distance-Preserving Tree (MRDPT) minimizes the total wi re length while maintaining minimal source to sink linear delay, makin g it suitable for high performance interconnect applications. This pap er studies problems in the construction of RDPTs, including the follow ing contributions. A new exact algorithm for a restricted version of t he problem in one quadrant with O(n(2)) time complexity is proposed. A novel heuristic algorithm, which uses optimally solvable sub-problems , is proposed for the problem in a single quadrant. The average and wo rst-case time complexity for the proposed heuristic algorithm are O(n( 3/2)) and O(n(3)), respectively. A 2-approximation of the quadrant mer ging problem is proposed. The proposed algorithm has time complexity O (alpha(2)T(n) + alpha(3)) for any constant alpha > 1, where T(n) is th e time complexity of the solution of the RDPT problem on one quadrant. This result improves over the best previous quadrant merging solution which has O(n(2)T(n) + n(3)) time complexity. We test our algorithms on randomly uniform point sets and compare our heuristic RDPT construc tion against a Minimum Cost Rectilinear Steiner (MRST) tree approximat ion algorithm. Our results show that RDPTs are competitive with Steine r trees in total wire-length when the number of terminals is less than 32. This result makes RDPTs suitable for VLSI routing applications. W e also compare our algorithm to the Rao-Shor RDPT approximation algori thm obtaining improvements of up to 10% in total wirelength. These com parisons show that the algorithms proposed herein produce promising re sults.