Minimal-perimeter polyominoes: chains, roots, and algorithms

Gill Barequet, Gil Ben-Shachar

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

A polyomino is a set of edge-connected squares on the square lattice. We investigate the combinatorial and geometric properties of minimal-perimeter polyominoes. We explore the behavior of minimal-perimeter polyominoes when they are “inflated,” i.e., expanded by all empty cells neighboring them, and show that inflating all minimal-perimeter polyominoes of a given area create the set of all minimal-perimeter polyominoes of some larger area. We characterize the roots of the infinite chains of sets of minimal-perimeter polyominoes which are created by inflating polyominoes of another set of minimal-perimeter polyominoes, and show that inflating any polyomino for a sufficient amount of times results in a minimal-perimeter polyomino. In addition, we devise two efficient algorithms for counting the number of minimal-perimeter polyominoes of a given area, compare the algorithms and analyze their running times, and provide the counts of polyominoes which they produce.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفAlgorithms and Discrete Applied Mathematics - 5th International Conference, CALDAM 2019, Proceedings
المحررونSudebkumar Prasant Pal, Ambat Vijayakumar
الصفحات109-123
عدد الصفحات15
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 2019
الحدث5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2019 - Kharagpur, الهند
المدة: ١٤ فبراير ٢٠١٩١٦ فبراير ٢٠١٩

سلسلة المنشورات

الاسمLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
مستوى الصوت11394 LNCS

!!Conference

!!Conference5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2019
الدولة/الإقليمالهند
المدينةKharagpur
المدة١٤/٠٢/١٩١٦/٠٢/١٩

All Science Journal Classification (ASJC) codes

  • !!Theoretical Computer Science
  • !!General Computer Science

بصمة

أدرس بدقة موضوعات البحث “Minimal-perimeter polyominoes: chains, roots, and algorithms'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا