Minimal Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard. - Archive ouverte HAL Accéder directement au contenu
Communication Dans Un Congrès Année : 2006

Minimal Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard.

Résumé

This paper deals with the complexity of the decomposition of a digital surface into digital plane segments (DPS for short). We prove that the decision problem (does there exist a decomposition with less than k DPS ?) is NP-complete, and thus that the optimisation problem (finding the minimal number of DPS) 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.
Fichier principal
Vignette du fichier
segmNP_revised.pdf (1.45 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00185124 , version 1 (06-11-2007)

Identifiants

  • HAL Id : hal-00185124 , version 1

Citer

Isabelle Sivignon, David Coeurjolly. Minimal Decomposition of a Digital Surface into Digital Plane Segments is NP-Hard.. Discrete Geometry for computer Imagery, Oct 2006, Szeged, Hungary. pp.674-685. ⟨hal-00185124⟩
153 Consultations
153 Téléchargements

Partager

Gmail Facebook X LinkedIn More