Document Open Access Logo

Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition)

Authors Gill Barequet, Gil Ben-Shachar

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2019.64.pdf
  • Filesize: 395 kB
  • 4 pages

Document Identifiers

Author Details

Gill Barequet
  • Technion - Israel Inst. of Technology, Haifa, Israel
Gil Ben-Shachar
  • Technion - Israel Inst. of Technology, Haifa, Israel

Funding

Work on this paper by both authors has been supported in part by ISF Grant 575/15 and by BSF Grant 2017684.

Cite As Get BibTex

Gill Barequet and Gil Ben-Shachar. Properties of Minimal-Perimeter Polyominoes (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 64:1-64:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.SoCG.2019.64

Abstract

In this video, we survey some results concerning polyominoes, which are sets of connected cells on the square lattice, and specifically, minimal-perimeter polyominoes, that are polyominoes with the minimal-perimeter from all polyominoes of the same size.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatoric problems
Keywords
  • Polyominoes
  • Perimeter
  • Minimal-Perimeter

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. Y. Altshuler, V. Yanovsky, D. Vainsencher, I.A. Wagner, and A.M. Bruckstein. On minimal perimeter polyminoes. In Proc. Conf. Discrete Geometry for Computer Imagery, pages 17-28. Springer, 2006. Google Scholar
  2. A. Asinowski, G. Barequet, and Y. Zheng. Enumerating polyominoes with fixed perimeter defect. In Proc. 9th European Conf. on Combinatorics, Graph Theory, and Applications, volume 61, pages 61-67, Vienna, Austria, August 2017. Elsevier. Google Scholar
  3. G. Barequet and G. Ben-Shachar. Properties of Minimal-Perimeter polyominoes. In International Computing and Combinatorics Conference, Qingdao, China, 2018. Springer. Google Scholar
  4. G. Barequet and G. Ben-Shachar. Minimal-Perimeter Polyominoes: Chains, Roots, and Algorithms. In Conference on Algorithms and Discrete Applied Mathematics, pages 109-123. Springer, 2019. Google Scholar
  5. G. Barequet, G. Rote, and M. Shalah. λ > 4: An improved lower bound on the growth constant of polyominoes. Comm. of the ACM, 59(7):88-95, 2016. Google Scholar
  6. S.R. Broadbent and J.M. Hammersley. Percolation processes: I. Crystals and Mazes. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 53, pages 629-641. Cambridge University Press, 1957. Google Scholar
  7. S.W. Golomb. Checker boards and polyominoes. The American Mathematical Monthly, 61(10):675-682, 1954. Google Scholar
  8. I. Jensen. Counting Polyominoes: A Parallel Implementation for Cluster Computing. In Peter M. A. Sloot, David Abramson, Alexander V. Bogdanov, Yuriy E. Gorbachev, Jack J. Dongarra, and Albert Y. Zomaya, editors, Proc. Int. Conf. on Computational Science, pages 203-212, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. Google Scholar
  9. D.A. Klarner. Cell growth problems. Canadian J. of Mathematics, 19:851-863, 1967. Google Scholar
  10. D.A. Klarner and R.L. Rivest. A procedure for improving the upper bound for the number of n-ominoes. Canadian J. of Mathematics, 25(3):585-602, 1973. Google Scholar
  11. N. Madras. A pattern theorem for lattice clusters. Annals of Combinatorics, 3(2):357-384, June 1999. Google Scholar
  12. D.H. Redelmeier. Counting polyominoes: Yet another attack. Discrete Mathematics, 36(2):191-203, 1981. Google Scholar
  13. N. Sieben. Polyominoes with minimum site-perimeter and full set achievement games. European J. of Combinatorics, 29(1):108-117, 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact