×

Detection of the discrete convexity of polyominoes. (English) Zbl 1019.52008

The paper deals with the notion of discrete convexity introduced by C. E. Kim and A. Rosenfeld [IEEE Trans. Pattern Anal. Mach. Intell. 4, 149-153 (1982; Zbl 0485.52007)]: a discrete region \(R\) is convex if its convex hull contains no discrete points of the complement of \(R\). A discrete region \(P\) is called polyomino if any couple of cells may be linked through a path containing only horizontal and vertical moves. A polyomino is \(hv\)-convex when cells of each row and each column are consecutive. Using only these definitions, the authors devise a simple algorithm to detect the convexity of a \(hv\)-polyomino. The main contribution of the paper under review is a linear algorithm for checking the convexity on the curve points of the border. Correctness of the method hinges on a new result on the construction of the convex hull of a discrete line segment. Preliminary conclusions on testing the discrete convexity of polyominoes by using the methods of constraint programming are reported.

MSC:

52A99 General convexity
05B50 Polyominoes
90C25 Convex programming
90C05 Linear programming

Citations:

Zbl 0485.52007

Software:

CHIP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aspvall, B.; Plass, M. F.; Tarjan, R. E., A linear-time algorithm for testing the truth of certain quantified boolean formulas, Inform. Process. Lett., 8, 3, 121-123 (1979) · Zbl 0398.68042
[2] E. Balogh, A. Kuba, C. Devenyi, A. Del Lungo, Comparison of algorithms for reconstructing hv; E. Balogh, A. Kuba, C. Devenyi, A. Del Lungo, Comparison of algorithms for reconstructing hv · Zbl 0990.65143
[3] E. Barcucci, S. Brunetti, A. Del Lungo, M. Nivat, Reconstruction of discrete sets from three or more X-rays, Fourth Italian Conference on Algorithms and Complexity (CIAC, 2000).; E. Barcucci, S. Brunetti, A. Del Lungo, M. Nivat, Reconstruction of discrete sets from three or more X-rays, Fourth Italian Conference on Algorithms and Complexity (CIAC, 2000). · Zbl 0971.68629
[4] Barcucci, E.; Del Lungo, A.; Nivat, M.; Pinzani, R., Reconstructing convex polyominoes from horizontal and vertical projections, Theoret. Comput. Sci., 155, 2, 321-347 (1996) · Zbl 0872.68134
[5] Barcucci, E.; Del Lungo, A.; Nivat, M.; Pinzani, R., Medians of polyominoes: a property for the reconstruction, Int. J. Imaging Systems Technol., 8, 69-77 (1998)
[6] Beldiceanu, N.; Contejean, E., Introducing global constraints in CHIP, J. Math. Comput. Modelling, 12, 97-123 (1994) · Zbl 0816.68048
[7] S. Brunetti, A. Daurat, Reconstruction of discrete sets from two or more projections in any direction, Proceedings of the Seventh International Workshop on Combinatorial Image Analysis (IWCIA, 2000), Caen, 2000, pp. 241-258.; S. Brunetti, A. Daurat, Reconstruction of discrete sets from two or more projections in any direction, Proceedings of the Seventh International Workshop on Combinatorial Image Analysis (IWCIA, 2000), Caen, 2000, pp. 241-258.
[8] S. Brunetti, A. Del Lungo, A. Daurat, An algorithm for reconstructing special lattice sets from their approximate X-rays. Discrete Geometry for Computer Imagery (DGCI 2000), Uppsala (Sweden), Lecture Notes in Computer Science, Vol. 1953, Springer, Berlin, 2000, pp. 113-125.; S. Brunetti, A. Del Lungo, A. Daurat, An algorithm for reconstructing special lattice sets from their approximate X-rays. Discrete Geometry for Computer Imagery (DGCI 2000), Uppsala (Sweden), Lecture Notes in Computer Science, Vol. 1953, Springer, Berlin, 2000, pp. 113-125. · Zbl 1043.68789
[9] S. Brunetti, A. Del Lungo, F. Del Ristoro, A. Kuba, M. Nivat, Reconstruction of 4- and 8-connected convex discrete sets from row and column projections, 1999, Lin. Algebra Appl., to appear.; S. Brunetti, A. Del Lungo, F. Del Ristoro, A. Kuba, M. Nivat, Reconstruction of 4- and 8-connected convex discrete sets from row and column projections, 1999, Lin. Algebra Appl., to appear. · Zbl 1007.65108
[10] J.-M. Chassery, A. Montanvert, Géométrie discrète en analyse d’images, Traité des nouvelles technologies, série Images, Hermes, 1991.; J.-M. Chassery, A. Montanvert, Géométrie discrète en analyse d’images, Traité des nouvelles technologies, série Images, Hermes, 1991.
[11] Chrobak, M.; Dürr, C., Reconstructing hv-convex polyominoes from orthogonal projections, Inform. Process. Lett., 69, 283-289 (1999) · Zbl 1002.68101
[12] I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, Thèse, Université Louis Pasteur, Strasbourg, 1995.; I. Debled-Rennesson, Etude et reconnaissance des droites et plans discrets, Thèse, Université Louis Pasteur, Strasbourg, 1995. · Zbl 0940.68147
[13] Debled-Rennesson, I.; Reveillès, J.-P., A linear algorithm for segmentation of digital curves, Int. J. Pattern Recognition, Artif. Intell., 9, 635-662 (1995)
[14] Del Lungo, A.; Nivat, N., (Herman, G. T.; Kuba, A., Reconstruction of Connected Sets from Two Projections (1999), Birkhäuser: Birkhäuser Boston), 163-188, (Chapter 7) · Zbl 0965.68114
[15] Del Lungo, A.; Nivat, M.; Pinzani, R., The number of convex polyominoes reconstructible from their orthogonal projections, Discrete Math., 157, 65-78 (1996) · Zbl 0856.05024
[16] M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, F. Berthier, The constraint logic programming language CHIP, Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Springer, Berlin, 1988, pp. 693-702.; M. Dincbas, P. Van Hentenryck, H. Simonis, A. Aggoun, T. Graf, F. Berthier, The constraint logic programming language CHIP, Proceedings of the International Conference on Fifth Generation Computer Systems, Tokyo, Springer, Berlin, 1988, pp. 693-702.
[17] Gardner, R. J.; Gritzmann, P., (Herman, G. T.; Kuba, A., Uniqueness and Complexity in Discrete Tomography (1999), Birkhäuser: Birkhäuser Boston), 85-113, (Chapter 4) · Zbl 0964.65146
[18] Hochstattler, W.; Loebl, M.; Moll, C., Generating convex polyominoes at random, Discrete Math., 153, 165-176 (1996) · Zbl 0854.05032
[19] A. Hübler, R. Klette, K. Voß, Determination of the convex hull of a finite set of planar points within linear time, Elektron. Inform. Kybernet., 1981, pp. 121-139.; A. Hübler, R. Klette, K. Voß, Determination of the convex hull of a finite set of planar points within linear time, Elektron. Inform. Kybernet., 1981, pp. 121-139. · Zbl 0534.68065
[20] Kim, C. E., Digital convexity, straightness and convex polygons, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4, 618-626 (1982) · Zbl 0491.68073
[21] Kim, C. E.; Rosenfeld, A., On the convexity of digital regions, Pattern Recognition, 5, 1010-1015 (1980)
[22] Kim, C. E.; Rosenfeld, A., Digital straight lines and convexity of digital regions, IEEE Trans. Pattern Anal. Mach. Intell., PAMI-4, 149-153 (1982) · Zbl 0485.52007
[23] A. Kuba, Reconstruction in different classes of 2D discrete sets, Discrete Geometry for Computer Imagery (DGCI’99), Marne-la-Vallée, Lecture Notes in Computer Science, Vol. 1568, Springer, Berlin, 1999, pp. 153-163.; A. Kuba, Reconstruction in different classes of 2D discrete sets, Discrete Geometry for Computer Imagery (DGCI’99), Marne-la-Vallée, Lecture Notes in Computer Science, Vol. 1568, Springer, Berlin, 1999, pp. 153-163.
[24] Kuba, A.; T. Herman, G., (Herman, G. T.; Kuba, A., Discrete Tomography: Foundations, Algorithms, and Applications (1999), Birkhäuser: Birkhäuser Boston) · Zbl 0946.00014
[25] Mariott, K.; Stuckey, P. J., Programming with Constraints: An Introduction (1998), MIT Press: MIT Press Reading, MA
[26] Minsky, M.; Papert, S., Perceptrons (1969), MIT Press: MIT Press Reading, MA
[27] J-.P. Reveillès, Structure des droites discrètes, Journées mathématique et informatique, Marseille-Luminy, Octobre 1989.; J-.P. Reveillès, Structure des droites discrètes, Journées mathématique et informatique, Marseille-Luminy, Octobre 1989.
[28] J-.P. Reveillès, Géométrie discrète, calculs en nombre entiers et algorithmique, Thèse d’état, Université Louis Pasteur, Strasbourg, 1991.; J-.P. Reveillès, Géométrie discrète, calculs en nombre entiers et algorithmique, Thèse d’état, Université Louis Pasteur, Strasbourg, 1991.
[29] I. Sivignon, Reconstruction de polyominos convexes par programmation par contraintes, Stage Report of “Magistère d”Informatique 1ère année, ENS Lyon”, realized at LORIA under the direction of Debled-Rennesson and A. Bockmayr, 1999.; I. Sivignon, Reconstruction de polyominos convexes par programmation par contraintes, Stage Report of “Magistère d”Informatique 1ère année, ENS Lyon”, realized at LORIA under the direction of Debled-Rennesson and A. Bockmayr, 1999.
[30] Slansky, J., Recognition of convex blobs, Pattern Recognition, 2, 3-10 (1970)
[31] G.J. Woeginger, The reconstruction of polyominoes from their orthogonal projections, Technical Report, Technische Universität Graz, 1996.; G.J. Woeginger, The reconstruction of polyominoes from their orthogonal projections, Technical Report, Technische Universität Graz, 1996. · Zbl 0996.68163
[32] T. Zajac, Reconstructing convex polyominoes using constraint programming, Master Thesis, Wroclaw University of Technology, Pologne.; T. Zajac, Reconstructing convex polyominoes using constraint programming, Master Thesis, Wroclaw University of Technology, Pologne.
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.