The Steiner tree problem for terminals on the boundary of a rectilinear polygon
Given a simple rectilinear polygon P with k sides and n terminals on its boundary, we present an O(k(3)n)-time algorithm to compute the minimal rectilinear Steiner tree lying inside P interconnecting the terminals. We obtain our result by proving structural properties of a selective set of minimal Steiner trees and exploiting them in a dynamic programming algorithm. (C) 2000 Elsevier Science B.V. All rights reserved.
rectilinear steiner tree dynamic programming homotpic routing