Abstract
The convexity of a discrete region is a property used in numerous domains of computational imagery. We study its detection in the particular case of polyominoes. We present a first method, directly relying on its definition. A second method, which is based on techniques for segmentation of curves in discrete lines, leads to a very simple algorithm whose correctness is proven. Correlatively, we obtain a characterisation of lower and upper convex hulls of a discrete line segment. Finally, we evoke some applications of these results to the problem of discrete tomography.
Chapter PDF
Similar content being viewed by others
References
B. Aspvall, M. F. Plass, and R. E. Tarjan. A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters, volume 8, number 3, pages 121–123, 1979. 50
E. Barcucci, A. Del Longo, M. Nivat, and R. Pinzani. Reconstructing convex polyominoes from horizontal and vertical projections. Theoretical Computer Science, volume 155, number 2, pages 321–347, 1996. 50
E. Barcucci, A. Del Longo, M. Nivat, and R. Pinzani. Medians of polyominoes: A property for the reconstruction. International Journal of Imaging Systems and Technology, volume 8, pages 69–77, 1998. 50
J-M. Chassery, A. Montanvert. Géométrie discrète en analyse d’images. Traité des nouvelles technologies, série Images, Hermes, 1991. 491, 493
M. Chrobak and C. Dürr. Reconstructing hv-convex polyominoes from orthogonal projections. Information Processing Letters, volume 69, pages 283–289, 1999. 502
I. Debled-Rennesson. Etude et reconnaissance des droites et plans discrets. Thèse. Université Louis Pasteur, Strasbourg, 1995. 491, 497, 498, 501
I. Debled-Rennesson and J. P. Reveillès. A linear algorithm for segmentation of digital curves. In International Journal of Pattern Recognition and Artificial Intelligence, volume 9, pages 635–662, Décembre 1995. 491, 495, 498, 501
A. Del Longo and M. Nivat and R. Pinzani. The number of convex polyominoes reconstructible from their orthogonal projections. Discrete Mathematics, volume 157, pages 65–78, 1996. 502
G. T. Herman and A. Kuba. Discrete Tomography. Birkhauser, 1999. 501
A. Hübler, R. Klette and K. Voβ. Determination of the Convex Hull of a Finite Set of Planar Points Within Linear Time. Elektronische Informationsverarbeitung und Kybernetik, pages 121–139, 1981. 503
C. E. Kim. Digital convexity, straightness and convex polygons. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume PAMI-4, pages 618–626, 1982. 492
C. E. Kim and A. Rosenfeld. On the convexity of digital regions. In Pattern Recognition, volume 5, pages 1010–1015, 1980. 492
C. E. Kim and A. Rosenfeld. Digital straight lines and convexity of digital regions. In IEEE Transactions on Pattern Analysis and Machine Intelligence, volume PAMI-4, pages 149–153, 1982. 492
M. Minsky and S. Papert. Perceptrons. In M. I. T. Press, 1969. 492
J. P. Reveillès. Géométrie discrète, calculs en nombre entiers et algorithmique. Thèse d’état. Université Louis Pasteur, Strasbourg, 1991. 495
J. P. Reveillès. Structure des droites discrètes. In Journées mathématique et informatique, Marseille-Luminy, Octobre 1989. 495
I. Sivignon. Reconstruction de polyominos convexes par programmation par contraintes. Rapport du stage de Magistère d’Informatique 1ère année, ENS Lyon, effectué au LORIA, 1999. 502
J. Slansky. Recognition of convex blobs. In Pattern Recognition, volume 2, pages 3–10, 1970. 492
G. J. Woeginger. The reconstruction of polyominoes from their orthogonal projections. Technical report, Technische Universität Graz, 1996. 502
T. Zajac. Reconstructing Convex Polyominoes using Constraint Programming. Master Thesis, Wroclaw University of Technology, Pologne. 502
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Debled-Rennesson, I., Jean-Luc, R., Rouyer-Degli, J. (2000). Detection of the Discrete Convexity of Polyominoes. In: Borgefors, G., Nyström, I., di Baja, G.S. (eds) Discrete Geometry for Computer Imagery. DGCI 2000. Lecture Notes in Computer Science, vol 1953. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44438-6_40
Download citation
DOI: https://doi.org/10.1007/3-540-44438-6_40
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-41396-7
Online ISBN: 978-3-540-44438-1
eBook Packages: Springer Book Archive