Tools for the Rectilinear Steiner Tree Problem

摘要

A Rectilinear Minimal Steiner Tree (RMST) for a set V of n points is a tree whichconnects the points of V using line segments parallel to the horizontal and vertical coordinate axes that has the shortest possible total length. Techniques are presented identifying connections that will be used in some RMST. These connections serve as a basis for an approximation algorithm. The identification methods are called contraction and clustering. Contractions identify line segments connected to the points on the enclosing rectangle of V and are totally independent of the further construction of the RMST. Clusturing identifies connections that can also be internal to the enclosing rectangle, but which are subject to restrictions posed by the further construction of the RMST. The approximation yields minimal Steiner trees for any set V of n less than or equal to 5 points, and trees with a length that is strictly less than 3/2 times the length of the RMST for larger n. The complexity of the constructing algorithms is O(n squared).