The Taub Faculty of Computer Science Events and Talks

A polyomino is an edge-connected set of cells on the square lattice. The problem of counting poyominoes dates back to the 1950s when it was studied in parallel in the fields of combinatorics and statistical physics. The study of polyominoes usually classifies polyominoes by their area, which is the number of cells the polyomino contains. Less explored is the perimeter of a polyomino, which is the set of empty cells adjacent to the polyomino. Several works studied the relation between the area of a polyomino and its perimeter. In this work we study the combinatoric and geometric properties of a special class of polyominoes, namely minimal-perimeter polyominoes, which, as the name suggests, are polyominoes with minimal perimeter for their area. In this talk we will present proofs for some geometric properties of minimal-perimeter polyominoes, which in turn, yield proofs of the combinatorial structure of minimal-perimeter polyominoes. In addition, these properties, allow us to devise efficient algorithms for counting the number of minimal-perimeter polyominoes.