Minimum decomposition of a digital surface into digital plane segments is NP-hard. (English) Zbl 1168.68049
Summary: 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 \(\lambda \) 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.
MSC:
| 68U10 | Computing methodologies for image processing |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Klette, R.; Rosenfeld, A., Digital straightness—a review, Discrete Applied Mathematics, 139, 1-3, 197-230 (2004) · Zbl 1093.68656 |
| [2] | Klette, R.; Rosenfeld, A., Digital geometry: Geometric methods for digital picture analysis, (Series in Comp. Graph. and Geom. Modeling (2004), Morgan Kaufmann) · Zbl 1064.68090 |
| [3] | Brimkov, V.; Coeurjolly, D.; Klette, R., Digital planarity—a review, Discrete Applied Mathematics, 155, 4, 468-495 (2007) · Zbl 1109.68122 |
| [4] | R. Klette, H.J. Sun, Digital planar segment based polyhedrization for surface area estimation, in: IWVF, 2001, pp. 356-366; R. Klette, H.J. Sun, Digital planar segment based polyhedrization for surface area estimation, in: IWVF, 2001, pp. 356-366 · Zbl 0985.65502 |
| [5] | Sivignon, I.; Dupont, F.; Chassery, J. M., Decomposition of a three-dimensional discrete object surface into discrete plane pieces, Algorithmica, 38, 1, 25-43 (2004) · Zbl 1072.68118 |
| [6] | Sivignon, Isabelle; Dupont, Florent; Chassery, Jean-Marc, Reversible vectorisation of 3D digital planar curves and applications, Image Vision and Computing, 25, 10, 1644-1656 (2007) |
| [7] | Feschet, F.; Tougne, L., On the min dss problem of closed discrete curves, Discrete Applied Mathematics, 151, 1-3, 138-153 (2005) · Zbl 1101.68904 |
| [8] | Françon, J.; Papier, L., Polyhedrization of the boundary of a voxel object, (8th DGCI. 8th DGCI, LNCS, vol. 1568 (1999), Springer-Verlag), 425-434 |
| [9] | I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, Ph.D. Thesis, Université Louis Pasteur, 1995; I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, Ph.D. Thesis, Université Louis Pasteur, 1995 · Zbl 0940.68147 |
| [10] | Goodman, J. E.; O’Rourke, J., Handbook of Discrete and Computational Geometry (1997), CRC Press · Zbl 0890.52001 |
| [11] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT Press: MIT Press Cambridge, MA · Zbl 1047.68161 |
| [12] | J.-P. Reveillès, Géométrie discrète, calcul en nombres entiers et algorithmique., Ph.D. Thesis, Université Louis Pasteur, Strasbourg 1991; J.-P. Reveillès, Géométrie discrète, calcul en nombres entiers et algorithmique., Ph.D. Thesis, Université Louis Pasteur, Strasbourg 1991 · Zbl 1079.51513 |
| [13] | Andres, E.; Acharya, R.; Sibata, C., Discrete analytical hyperplanes, Graphical Models and Image Processing, 59, 5, 302-309 (1997) |
| [14] | Brimkov, V., Discrete volume polyhedrization: Complexity and bounds on performance, (Computational Methodology of Objects Represented in Images: Fundamentals, Methods and Applications, Proc. of the International Symposium CompIMAGE’06 (2006), Taylor and Francis Publisher: Taylor and Francis Publisher Coimbra, Portugal) |
| [15] | C. Worman, Decomposing polygons into diameter bounded components, in: Canadian Conference on Computational Geometry, CCCG’03, 2003, pp. 103-106; C. Worman, Decomposing polygons into diameter bounded components, in: Canadian Conference on Computational Geometry, CCCG’03, 2003, pp. 103-106 |
| [16] | B. Chazelle, D.P. Dobkin, N. Shouraboura, A. Tal, Strategies for polyhedral surface decomposition: An experimental study, in: Symp. on Computational Geometry, 1995, pp. 297-305; B. Chazelle, D.P. Dobkin, N. Shouraboura, A. Tal, Strategies for polyhedral surface decomposition: An experimental study, in: Symp. on Computational Geometry, 1995, pp. 297-305 · Zbl 1133.52305 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
