TILING OF FIGURES OF PLANES WITHOUT HOLES USING DOMINOES - GRAPHICAL BASIS OF THE THURSTON ALGORITHM, PARALLELIZATION, UNIQUENESS AND DECOMPOSITION [French]

摘要

We consider the problem of tiling with dominoes pictures of the plane without holes. Known results and generalizations of the problem can be found in [5, 7]. Here, a picture is a subset of unit squares of the plane (considered as Z x Z). It is easy to see that a necessary condition for the existence of a tiling for a chessboard-like coloured picture is that there is an equal number of black squares and of white ones in the picture (balanced picture) This condition is not sufficient as we can see while analysing the (balanced) picture in Fig. 1. More deeply, the impossibility of tiling this picture is due to the existence of the line abe which delimits a subpicture, under abc, with the following properties: (1) there are more black squares than white ones, (2) the line abc runs alongside white squares of the subpicture. Such a subpicture will be called an obstruction to tiling. If a picture has no obstruction to tiling, then it is tilable. In fact, this condition corresponds to the classical Hall's condition for matchings in bipartite graphs. We express that in another way. The boundary path of a picture F (without holes) determines a height function h on its vertices, up to constant: if (s(0), s(1),...,s(p)) is the sequence of vertices of the boundary path, with s(p) = s(0), let us define: - h(s(0)) = k, where k is some integer, - for i = 1,...,p: [GRAPHICS] Such a function will be called a height function oil the boundary of the picture. Let F be a picture, we associate with F the white oil the left directed graph G in the following way: the vertices of G are the vertices of F and the arcs of G correspond to edges of F oriented in such a way that a white square is always on the left-hand side of each are. Let d(s, t) denote the distance from a vertex s to a vertex t in G (the length of a shortest path from s to t in G. Let us define a height function ii on the vertices of F, associated with a height function g on the boundary C of F: for every vertex t of F, we set h(t) = min {g(s) + d(s,t)s vertex of C}. Such a Function will be called a height function on the picture. Note that for every vertex t of C we have h(t) less than or equal to g(t). The inequality h(t) < g(t) is possible and it corresponds to the existence of an obstruction to tiling in the picture. So the main result is: Theorem 1. Let F be a picture, C the boundary of F, g a height function on C, h a height function on F associated with g. The picture is tilable if and only if for every s is an element of C, we have h(s) = g(s). Moreover, if F is tilable, the edges tt' such that h(t) - h(t') = 1 define a tiling of F. Examples. See Figs. 3 and 4. This result allows us to find again the Thurston'algorithm [6]. Tn fact, the height function is equal to a distance in an extension of the white on the left graph (Theorem 2). It is then possible to calculate the height function h on F, and so calculate a tiling of F if the condition h(s) = g(s) for every s is an element of C is true, by a classical Breadth First Search algorithm (note that the height function g on C is easy to calculate). The whole algorithm is linear. More interesting is the possibility of a parallelization of this algorithm, by means of a parallelization of Breadth First Search (see [4]). The obtained parallel algorithm for tiling a picture without holes is in O (log it) time using n(3) processors on a PRAM model. This result is rather unexpected apart from the new point of view given here. We give next a canonical decomposition theorem for pictures' tilings. Let F be a tilable picture with boundary C. We define a fracture path of F as a path in the white on the left directed graph from a vertex se C to a vertex s' is an element of C such that g(s') = g(s) + l, where l is the length of the path. A fracture edge is a picture's edge which is on a fracture path, and the fracture graph is the graph induced by fracture edges. It is to note that a fracture edge is never covered by a domino in a picture's t