Name
Abstract | ||
|---|---|---|
Given two “bars”, a horizontal one, and a vertical one (both of length at least two), we 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. Given a general pair of bars, we give 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. Finally, 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 covering a “canonical” rectangle . |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1016/0925-7721(94)00015-N | Comput. Geom. |
Keywords | Field | DocType |
tiling figure,np-complete,tiling,bars,np complete,decision problem | Discrete mathematics,Decision problem,Rhombille tiling,Combinatorics,Square tiling,Trihexagonal tiling,Hexagonal tiling,Arrangement of lines,Rectangle,If and only if,Mathematics | Journal |
Volume | Issue | ISSN |
5 | 1 | Computational Geometry: Theory and Applications |
Citations | PageRank | References |
16 | 1.26 | 4 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Danièle Beauquier | 1 | 284 | 31.44 |
| Maurice Nivat | 2 | 1261 | 277.74 |
| Eric Rémila | 3 | 329 | 45.22 |
| Mike Robson | 4 | 16 | 1.26 |