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
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - 2019
אירוע5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2019 - Kharagpur, הודו
משך הזמן: 14 פבר׳ 201916 פבר׳ 2019

סדרות פרסומים

שםLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
כרך11394 LNCS

כנס

כנס5th International Conference on Algorithms and Discrete Applied Mathematics, CALDAM 2019
מדינה/אזורהודו
עירKharagpur
תקופה14/02/1916/02/19

ASJC Scopus subject areas

  • ???subjectarea.asjc.2600.2614???
  • ???subjectarea.asjc.1700.1700???

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Minimal-perimeter polyominoes: chains, roots, and algorithms'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי