On the minimum corridor connection and other generalized geometric problems

H.L. Bodlaender, C. Feremans, A. Grigoriev, E. Penninkx, R.A. Sitters, T. Wolle

Research output: Contribution to journalArticleAcademicpeer-review

17 Citations (Scopus)
1 Downloads (Pure)

Abstract

In this paper we discuss the complexity and approximability of the minimum corridor connection 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 decomposition such that every room is incident to a vertex of the tree. We show that the problem is strongly NP-hard and give a subexponential time exact algorithm. For the special case when the room connectivity graph is k-outerplanar the algorithm running time becomes cubic. We develop a polynomial time approximation scheme for the case when all rooms are fat and have nearly the same size. When rooms are fat but are of varying size we give a polynomial time constant factor approximation algorithm.
Original languageEnglish
Pages (from-to)939-951
JournalComputational Geometry
Volume42
Issue number9
DOIs
Publication statusPublished - 2009

Fingerprint

Dive into the research topics of 'On the minimum corridor connection and other generalized geometric problems'. Together they form a unique fingerprint.

Cite this