Algorithms for Plane Steiner Tree Problems

Topological network design is the process of planning the layout of a network subject to constraints on topology. Applications include the design of transportation and communication networks where the construction costs typically are associated with the nodes and/or edges of the network. The Steiner tree problem is one of the fundamental topological network design problems. The problem is to interconnect (a subset of) the nodes such that there is a path between every pair of nodes while minimizing the total cost of selected edges. Originally, the Steiner tree problem was stated as a purely geometric problem: Given a set of points (terminals) in the plane, construct a tree interconnecting all terminals such that the total length of all line segments is minimized. In the Euclidean Steiner tree problem, the length of a line segment is the usual Euclidean (or L 2 ) distance between the endpoints of the segment. Correspondingly, in the rectilinear Steiner tree problem distances are measured using the rectilinear (or L1) distance metric.