Polynomial Time Algorithms for the Rectilinear Steiner Tree Problem

Abstract

The rectilinear Steiner tree problem has been proven to be NP-hard. However, an exact polynomial time algorithm may exist if the given point set has a special configuration (geometric structure). In this paper we survey the known algorithms for such configurations, including small point sets, points on a rectangular boundary, points on parallel lines and sets of points that are constrained to lie on curves.