On the exhaustive generation of discrete figures with connectivity constraints

Hugo Tremblay; Julien Vernay

doi:10.2478/puma-2022-0016

.blurhash-client-img { display: none !important; }

On the exhaustive generation of discrete figures with connectivity constraints

Pure Mathematics and Applications

Volume 30 (2022): Issue 1 (June 2022)

By: Hugo Tremblay and Julien Vernay

Open Access

|Jun 2022

Abstract

This paper deals with a generalization of polyominoes called (a, b)-connected discrete figures, where a and b respectively denotes the connectivity of the foreground (i.e. black pixels) and background (i.e. white pixels). Formally, a finite set of pixels P is (a, b)-connected if P is a-connected and P̄ is b-connected. By adapting a combinatorial structure enumeration algorithm due to Martin, we successfully generate (a, b)-connected discrete figures up to size n = 18.

References

[1] P. Bose, V. Dujmovic, F. Hurtado and P. Morin, Connectivity-preserving transformations of binary images, Comput. Vis. Image Underst., 113 (2009) 1027–1038.
Search in Google Scholar Back to article
[2] Z. M. Du, F. Y. Ye, H. Shi and G. P. Zhu, A fast recovery method of 2D geometric compressed sensing signal, Circ. Syst. Signal Pr., 34 (2015) 1711–1724.
Search in Google Scholar Back to article
[3] S. W. Golomb, Polyominoes, Charles Scribners’ Sons, 1965.
Search in Google Scholar Back to article
[4] S. W. Golomb, Polyominoes: Puzzles, Patterns, Problems, and Packings, Princeton University Press, 1994.10.1515/9780691215051
Search in Google Scholar Back to article
[5] I. Jensen and A. J. Guttmann, Self-avoiding polygons on the square lattice, J. Phys. A, 32 (1999) 4867–4876.
Search in Google Scholar Back to article
[6] M. Kobilarov, M. Desbrun, J. Marsden and G. Sukhatme, A discrete geometric optimal control framework for systems with symmetries, Proceedings of Robotics: Science and Systems (2007) Atlanta, GA, USA, June.10.15607/RSS.2007.III.021
Search in Google Scholar Back to article
[7] P. M. Lam, On Monte Carlo generation and study of anisotropy of lattice animals, J. Phys. A, 19 (1986) L155.10.1088/0305-4470/19/3/011
Search in Google Scholar Back to article
[8] J. L. Martin, Computer techniques for evaluating lattice constants, in: Domb, C., Green, M. S. (Eds.), Phase Transitions and Critical Phenomena, vol. 3, Academic Press, London, 1974, pp. 97—112.
Search in Google Scholar Back to article
[9] S. J. Redner, A Fortran program for cluster enumeration, J. Stat. Phys., 29 (1982) 309–315.
Search in Google Scholar Back to article
[10] T. Sunada, Topological Crystallography, Springer, 2013.10.1007/978-4-431-54177-6
Search in Google Scholar Back to article
[11] J. Vernay, GitHub Repository: discrete-figures, version 1.1.0 (2022), https://github.com/JVernay/discrete-figures.
Search in Google Scholar Back to article

Articles in this issue

DOI: https://doi.org/10.2478/puma-2022-0016 | Journal eISSN: 1788-800X

Journal RSS Feed

Language: English

Page range: 106 - 112

Submitted on: Mar 31, 2022

Accepted on: May 15, 2022

Published on: Jun 18, 2022

Published by: Corvinus University of Budapest

In partnership with: Paradigm Publishing Services

Publication frequency: 4 issues per year

Keywords:

algorithm,

exhaustive generation,

discrete figure,

digital geometry

Related subjects:

Computer sciences,

Theoretical computer sciences,

Business and economics,

Mathematics and statistics for economists,

Mathematics,

Analysis,

Differential equations and dynamical systems

© 2022 Hugo Tremblay, Julien Vernay, published by Corvinus University of Budapest
This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Volume 30 (2022): Issue 1 (June 2022)