On Rectilinear Distance-Preserving Trees

Given a set of terminals on the plane N={s,ν1,…,νn}, with a source terminal s, aRectilinear Distance-Preserving Tree (RDPT) T(V, E) is defined as a tree rooted at s,connecting all terminals in N. An RDPT has the property that the length of every sourceto sink path is equal to the rectilinear distance between that source and sink. A Min-Cost Rectilinear Distance-Preserving Tree (MRDPT) minimizes the total wire lengthwhile maintaining minimal source to sink linear delay, making it suitable for highperformance interconnect applications