Generating convex polyominoes at random (Q1917521)

A polyomino is a connected finite union of squares from the square grid in the plane. It is convex if its intersection with each horizontal or vertical line is connected. The authors describe a new recursion formula for the number \(P_n\) of convex polyominoes of perimeter \(n\). They construct a bijection from \(\{1,\dots, P_n\}\) into the set of all such polyominoes which leads to a polynomial time algorithm that generates them at random. Similar results are also obtained for the sets of convex polyominoes with fixed area or with fixed area and perimeter. The authors also present a simple linear time probabilistic algorithm which uniformly generates convex polyominoes of a given perimeter with asymptotic probability 0.5.