Generating convex polyominoes at random
type: Item
instance of: scholarly article
title: Generating convex polyominoes at random
zbMATH Open document ID: 0854.05032
DOI: 10.1016/0012-365X(95)00134-I
author: Winfried. Hochstättler
author: Christoph Moll
author: Martin Loebl
published in: Discrete Mathematics
publication date: 1996-09-03T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05B50
zbMATH DE Number: 897602
zbMATH Keywords: polyomino
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: convex polyominoes
zbMATH Keywords: probabilistic algorithm
reviewed by: Egon Schulte
MaRDI profile type: Publication
cites work: Convex n-ominoes
cites work: Combinatorial properties of polyominoes
cites work: Tiling with polyominoes and combinatorial group theory
cites work: Algebraic languages and polyominoes enumeration
cites work: Polyominoes which tile rectangles
cites work: The number of convex polyominoes with given perimeter
cites work: Q4305245
cites work: On the number of certain lattice polygons
description: scientific article; zbMATH DE number 897602