Back to Search
Start Over
Minimum decomposition of a digital surface into digital plane segments is NP-hard
- Source :
-
Discrete Applied Mathematics . Feb2009, Vol. 157 Issue 3, p558-570. 13p. - Publication Year :
- 2009
-
Abstract
- Abstract: This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPSs for short). We prove that the decision problem (does there exist a decomposition with less than DPSs?) is NP-complete, and thus that the optimization problem (finding the minimum number of DPSs) is NP-hard. The proof is based on a polynomial reduction of any instance of the well-known 3-SAT problem to an instance of the digital surface decomposition problem. A geometric model for the 3-SAT problem is proposed. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 0166218X
- Volume :
- 157
- Issue :
- 3
- Database :
- Academic Search Index
- Journal :
- Discrete Applied Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 35557284
- Full Text :
- https://doi.org/10.1016/j.dam.2008.05.028