טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentMoffie Micha
SubjectCounting Polyominoes in Two and Three Dimensions
DepartmentDepartment of Computer Science
Supervisor Professor Gill Barequet


Abstract

A polyomino, also known in the literature as a “lattice animal”, of order n is an edge-connected set of n squares on a regular square lattice. Three-dimensional polyominoes are called polycubes [Lu71]; a polycube of size n is a face-connected set of n cubes in a Euclidean three-dimensional space. Recently, I. Jensen [Je01] published a novel transfer-matrix algorithm for computing the number of two-dimensional polyominoes in a rectangular lattice. However, his estimation of the computational complexity of the algorithm was based only on empirical evidence. We provide a rigorous computation that roughly confirms Jensen's estimation of the computational complexity of his algorithm. This is done by analyzing the number of some class of strings, which play a significant role in the algorithm. It turns out that this number is closely related to Motzkin’s numbers [Mo48]. We also present two extensions of Jensen's algorithm, designed to reuse previously-computed results and reduce the number of iterations of the algorithm. We then generalize Jensen’s transfer-matrix algorithm to three dimensions, we present a scheme for encoding boundaries of three-dimensional polycubes and derive suitable updating rules. In addition, we describe an efficient implementation of Redelmeier's serial algorithm [Rede81], which can actually fit any dimension, and use it for counting polycubes. We confirm Lunnon's results [Lu71] for polycubes, and unpublished results found on the Internet (up to size 17). We also provide the number of polycubes of size 18, which, to the best of our knowledge, has never been published in the literature.