Hochstättler, Winfried and Loebl, Martin and Moll, Christoph (1996) Generating Convex Polyominoes at Random.
Published In: Formal power series and algebraic combinatorics ; Conference proceedings ; 21 - 25 june 1993, Discrete mathematics. 153 Elsevier 1996, pp. 165-176.

Abstract

We give a new recursion formula for the number of convex polyominoes with fixed perimeter. From this we derive a bijection between an intervall of natural numbers and the polyominoes of given perimeter. This provides a possibility to generate such polyominoes at random in polynomial time. Our method also applies for fixed area and even when fixing both, perimeter and area. In the second part of the paper we present a simple linear time probabilistic algorithm which uniformly generates convex polyominoes of given perimeter with asymptotic probability 0.5.

Actions:

Download:	Postscript - Preprinted Version Download (188kB) | Preview
Editorial actions:	View Item (Login required)