The Steiner tree problem for terminals on the boundary of a rectilinear polygon (Q1566725)

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.