Random Generation of hv-Convex Polyominoes with Given Horizontal Projection

• Autorzy: Hantos, N. , Balázs, P.
• Języki publikacji: EN

Abstrakty

EN

We provide a quadratic-time algorithm for generating hv-convex polyominoes according to a given horizontal projection. The method can be used to generate hv-convex polyominoes with the prescribed projection and with a fixed or arbitrary horizontal dimension, from a uniform random distribution.

Słowa kluczowe

EN

hv-convex polyomino; horizontal projection; random generation; binary tomography

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2014
• Tom: Vol. 135, nr 1/2
• Strony: 103--115
• Opis fizyczny: Bibliogr. 14 poz., rys., wykr.

Twórcy

autor

Hantos, N.

• Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary,

autor

Balázs, P.

• Department of Image Processing and Computer Graphics, University of Szeged, Árpád tér 2. H-6720, Szeged, Hungary,

Bibliografia

• [1] E. Balogh, A. Kuba, Cs. Dévényi, A. Del Lungo, Comparison of algorithms for reconstructing hv-convex discrete sets, Lin. Alg. and Its Appl. 339(1–3) (2001) 23–35.
• [2] E. Barcucci, A. Del Lungo, M. Nivat, R. Pinzani, Medians of polyominoes: A property for the reconstruction, Int. J. Imaging Syst. and Techn. 9 (1998) 69–77.
• [3] S. Brunetti, A. Daurat, Random generation of Q-convex sets, Theor. Comput. Sci. 347(1–2) (2005) 393–414.
• [4] 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, Lin. Alg. and Its Appl. 339(1–3) (2001) 37–57.
• [5] M. Chrobak, Ch. Dürr, Reconstructing hv-convex polyominoes from orthogonal projections, Information Processing Letters 69(6) (1999) 283–289.
• [6] A. Del Lungo, Polyominoes defined by two vectors, Theor. Comput. Sci. 127 (1994) 187–198.
• [7] A. Del Lungo, E. Duchi, A. Frosini, S. Rinaldi, Enumeration of convex polyominoes using the ECO method, Discrete Mathematics and Theoretical Computer Science, Proceedings (2003) 103–116.
• [8] A. Del Lungo, E. Duchi, A. Frosini, S. Rinaldi, On the generation and enumeration of some classes of convex polyominoes, The Electronic Journal of Combinatorics 11 (2004) R60.
• [9] A. Del Lungo, M. Nivat, R. Pinzani, The number of convex polyominoes recostructible from their orthogonal projections, Discrete Math. 157 (1996) 65–78.
• [10] S.W. Golomb, Polyominoes, Charles Scriber’s Sons, New York, 1965.
• [11] N. Hantos, P. Balázs, Reconstruction and enumeration of hv-convex polyominoes with given horizontal projection, Lecture Notes in Computer Sciences 8258 (2013) 100–107.
• [12] G.T. Herman, A. Kuba (Eds.), Discrete Tomography: Foundations, Algorithms and Applications, Birkhäuser, Boston, 1999.
• [13] G.T. Herman, A. Kuba (Eds.), Advances in Discrete Tomography and its Applications, Birkhäuser, Boston, 2007.
• [14] W. Hochstättler, M. Loebl, C. Moll, Generating convex polyominoes at random, Discrete Math. 153 (1996) 165–176.

Identyfikatory

DOI

10.3233/FI-2014-1114