M.Sc Student | Moffie Micha |
---|---|

Subject | Counting Polyominoes in Two and Three Dimensions |

Department | Department of Computer Science |

Supervisor | Professor Gill Barequet |

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.