Name
Abstract | ||
|---|---|---|
We give a new recursion formula for the number of convex polyominoes with fixed perimeter. From this we derive a bijection between an interval 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. |
Year | DOI | Venue |
|---|---|---|
1996 | 10.1016/0012-365X(95)00134-I | FPSAC '93 Proceedings of the 5th conference on Formal power series and algebraic combinatorics |
Keywords | Field | DocType |
generating convex polyominoes,linear time,polynomial time,probabilistic algorithm | Randomized algorithm,Discrete mathematics,Natural number,Combinatorics,Bijection,Polyomino,Convex polygon,Regular polygon,Time complexity,Recursion,Mathematics | Journal |
Volume | Issue | ISSN |
153 | 1-3 | 0012-365X |
Citations | PageRank | References |
16 | 1.27 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Winfried Hochstättler | 1 | 209 | 30.96 |
| Martin Loebl | 2 | 152 | 28.66 |
| Christoph Moll | 3 | 16 | 1.27 |