A Polynomial Time Algorithm for Rectilinear Steiner Trees with Terminals Constrained to Curves

The rectilinear Steiner problem is the problem of constructing the shortest rectilinear network in the plane connecting a given set of points, called terminals. The problem is known to be NP-complete in general. In this paper, we show that there is a polynomial time algorithm for solving the rectilinear Steiner problem for the case where terminals are constrained to lie on almost any fixed set of simple disjoint compact curves. © 1999 John Wiley & Sons, Inc. Networks 33: 145-155, 1999