Equispreading Tree in Manhattan Distance

The equispreading tree on the plane with Manhattan distance, which is a Steiner tree such that all paths from the root to all leaves have the same length, is analyzed. This problem is not only fundamental in computational geometry but also critical for equidistant routings in VLSI clock design. Several characteristics for the trees are discussed together with an algorithm constructing equispreading trees in the bottom-up fashion. This algorithm achieves linear time and space complexity with respect to the number of leaves, and minimizes the path length from the root to leaves. Furthermore, this paper shows that the shortest-path-length equispreading trees are related to the smallest enclosing circles in Manhattan distance.