✦ LIBER ✦

Tiling pictures of the plane with dominoes

✍ Scribed by J.C. Fournier

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 452 KB
Volume: 165-166
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00179-3

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of tiling with dominoes pictures of the plane. in theoretical and algorithmic aspects. For generalities and other tiling problems, see for example Refs. Beauquier et al. (1995), Conway and Lagarias (1990). Kannan and Soroker (1992), Kenyon (1992), and Beauquier (1991). The pictures which are considered here may have holes, but uniquely haltrnced holes. that is every hole, if chessboard-like coloured, has an equal number of black squares and of white ones. We give an algorithmic characterization of tilable pictures and a canonical decomposition into 'strongly' tilable subpictures. The given algorithm is linear as far the considered pictures have a finite number of (balanced) holes. In the same hypothesis there is a good parallel algorithm (in class NC). Graphical extension of the used method (Izeiyhts' mc~thf) is applied to a class of bipartite planar graphs. The particular case of without holes pictures is developed in Fournier (1996).

As far as I know, the results in this paper are new, except the notions and the theorem in Section 2, which are substantially present in Thurston (1990).

📜 SIMILAR VOLUMES

Domino tilings of rectangles with fixed

Domino tilings of rectangles with fixed width

✍ David Klarner; Jordan Pollack 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 761 KB

Let t(k, n) denote the number of ways to tile a C x n rectangle with 1 x 2 rectangles (called dominoes). We show that for each fixed k the s( quence tk = (t(k, O), t(k, I), . . .) satisfies a difference equation (linear, homogeneous, and w ith constant coefficients). Furthermore, a computational met

Isohedral Polyomino Tiling of the Plane

✍ K. Keating; A. Vince 📂 Article 📅 1999 🏛 Springer 🌐 English ⚖ 266 KB

Segmentation of pictures into regions wi

Segmentation of pictures into regions with a tile-by-tile method

✍ Jason D. Browning; Steven L. Tanimoto 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 529 KB

On tilings of the plane

✍ Andreas W. M. Dress; Daniel Huson 📂 Article 📅 1987 🏛 Springer 🌐 English ⚖ 746 KB

The paper discusses homeomorphic types of (periodic) filings of the plane in terms of their associated Delaney symbol. Such a symbol consists of a (finite) set ~ on which three involutions ao,al and tr2 act from the right such that troa ~ = a2ao and there are two maps mol ,m12 :~ ~ ~ satisfying cert

Quadri-tilings of the Plane

✍ Béatrice de Tilière 📂 Article 📅 2006 🏛 Springer 🌐 English ⚖ 364 KB

An O(n log n)-algorithm for fi

An O(n log n)-algorithm for finding a domino tiling of a plane picture whose number of holes is bounded

✍ Nicolas Thiant 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 702 KB

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