Tiling figures of the plane with two bars (Q1346250): Difference between revisions

Polyominoes and more generally pictures drawn on a plane grid are a subject which fascinated mathematicians for a long time. They appeared of great interest for computer science in many research fields: computational geometry, data organization in parallel computer architecture, formal languages theory, decidability theory, and so on. In this paper the authors have focused their attention on the problem of codification and related questions. They have considered a number of problems relating to tilings of plane finite figures by non-overlapping bars. A figure consists of a number of unit squares and they are concerned with bars chosen from a pair of allowed types \(h_ \ell\) (covering \(\ell \geq 2\) horizontally contiguous squares) and \(v_ m\) (covering \(m\geq 2\) vertically contiguous squares). Given a finite figure and a particular pair of bar types, the authors are interested in deciding whether a tiling exists, whether it is unique and in actually finding a tiling if one does exist. Similar problems have been studied in the past concerning mainly more complex tile shape than these bars but often simpler figures than these arbitrary ones (squares, quadrants or the whole plane). Results proved have included undecidability of tiling the plane with a given finite set of tiles, NP-completeness of tilings of finite figures, and undecidability of tile codes, that is finite sets of tiles for which a tiling of any finite figure must be unique. Since a non-connected figure is (uniquely) tilable if and only if each of its connected components is (uniquely) tilable, the authors have considered only connected figures. A more significant distinction concerns the existence of holes. It turns out that absence of holes plays an important role. The existence of a tiling can be decided in \(P\) for the simplest case \(h_ 2\), \(v_ 2\) (the dominoes), with or without holes. For all other pairs of bar types this problem is NP-complete for finite figures with holes and has recently been proved to be in \(P\) for those without holes. For the simple case of two dominoes, the authors showed efficient algorithms for certain problems. Finding a tiling, if one exists, can be performed efficiently in general and even in linear time in the size of the figure for certain classes of figures. There is also a linear time algorithm for deciding existence of a unique tiling for finite figures without holes. For the case of a general pair of bar types \(h_ \ell\), \(v_ m\) and finite figures without holes, the authors gave two results on unique tilings. Namely they gave a necessary condition for a finite figure to have a unique tiling and also a necessary and sufficient condition that a given tiling is in fact unique. Finally to conclude given two ``bars'', a horizontal one, and a vertical one (both of length at least two), they are interested in the following decision problem: Is a finite figure drawn on a plane grid tilable with these bars? It turns out that if one of the bars has length at least three, the problem is NP- complete. If bars are dominoes, the problem is in \(P\), and even linear (in the size of the figure) for certain classes of figures. Thus given a general pair of bars, the authors established two results: (1) a necessary condition to have a unique tiling for finite figures without holes, (2) a linear algorithm (in the size of the figure) deciding whether a unique tiling exists, and computing this one if it does exist. And thus given a tiling of a figure (not necessarily finite), this tiling is the unique one for the figure if and only if there exists no subtiling of a ``canonical'' rectangle.