Complexity of the minimum-length corridor problem

AbstractWe study the Minimum-Length Corridor (MLC) problem. Given a rectangular boundary partitioned into rectilinear polygons, the objective is to find a corridor of least total length. A corridor is a set of line segments each of which must lie along the line segments that form the rectangular boundary and/or the boundary of the rectilinear polygons. The corridor is a tree, and must include at least one point from the rectangular boundary and at least one point from the boundary of each of the rectilinear polygons. We establish the NP-completeness of the decision version of the MLC problem even when it is restricted to a rectangular boundary partitioned into rectangles