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.
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.
Download: |
Download (188kB) | Preview |
---|---|
Editorial actions: | ![]() |
Item Type: | Proceedings article |
---|---|
Citations: | 25 (Google Scholar) | 16 (Web of Science) |
Uncontrolled Keywords: | algorithms enumeration polyomino |
Subjects: |
|
Divisions: | Mathematical Institute |
Related URLs: |
ZAIK Number: | zpr92-112 |
---|---|
Depositing User: | Winfried Hochstättler |
Date Deposited: | 02 Apr 2001 00:00 |
Last Modified: | 19 Jan 2012 10:28 |
URI: | http://e-archive.informatik.uni-koeln.de/id/eprint/112 |