Back to Search
Start Over
On the minimum corridor connection problem and other generalized geometric problems
- Source :
-
Computational Geometry . Nov2009, Vol. 42 Issue 9, p939-951. 13p. - Publication Year :
- 2009
-
Abstract
- 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. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 09257721
- Volume :
- 42
- Issue :
- 9
- Database :
- Academic Search Index
- Journal :
- Computational Geometry
- Publication Type :
- Academic Journal
- Accession number :
- 43175510
- Full Text :
- https://doi.org/10.1016/j.comgeo.2009.05.001