✦ LIBER ✦
An O(n log n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded
✍ Scribed by Nicolas Thiant
- Publisher
- Elsevier Science
- Year
- 2003
- Tongue
- English
- Weight
- 702 KB
- Volume
- 303
- Category
- Article
- ISSN
- 0304-3975
No coin nor oath required. For personal study only.
✦ Synopsis
We consider the problem of tiling a plane picture with dominoes, this picture can be with holes or without holes. We give a necessary and su cient condition for the existence of such a tiling and then we deduce an algorithm to decide whether a picture is tileable or not and if it is, to determine a tiling. This algorithm runs in O(kn + n log n) time, where n and k are the respective numbers of cells and holes. We also propose a simpliÿed version of this algorithm which is linear in the area enclosed by the outer boundary, provided the picture has a bounded number of holes.