Complexity of the minimum-length corridor problem (Q876503)

The authors study the minimum-length corridor (MLC) problem and some of its variants. More precisely, given a rectangular boundary partitioned into rectilinear polygons, the problem consists in finding 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. In this paper, it is established that the MLC problem is NP-complete.