On the minimum corridor connection problem and other generalized geometric problems

摘要

In this paper we discuss the complexity and approximability of the minimum corridorconnection problem where, given a rectilinear decomposition of a rectilinear polygon into"rooms", one has to find the minimum length tree along the edges of the decompositionsuch that every room is incident to a vertex of the tree. We show that the problem isstrongly NP-hard and give a subexponential time exact algorithm. For the special casewhen the room connectivity graph is k-outerplanar the algorithm running time becomescubic. We develop a polynomial time approximation scheme for the case when all roomsare fat and have nearly the same size. When rooms are fat but are of varying size we givea polynomial time constant factor approximation algorithm.