We consider the following fundamental network design problem, denoted the Steiner tree problem in the plane: 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₂) distance between the endpoints of the segment. Correspondingly, in the rectilinear Steiner tree problem distances are measured using the rectilinear (or L₁) distance metric. In this talk, we will describe recent exact and heuristic algorithms for these two problems. The new algorithms allow the exact solution of real-life instances with more than 2000 terminals. Applications of the rectilinear problem in VLSI design are given. Also, we give a short introduction to the important generalization in which a set of polygonal obstacles has to be avoided by the tree interconnecting the terminals.

Host: Jørgen Bang-Jensen