Generating Convex Polyominoes at Random

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.


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.

Download: [img] Postscript - Preprinted Version
Download (188kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr92-112
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Jan 2012 10:28