{
"id": "1710.04640",
"version": "v1",
"published": "2017-10-12T17:52:22.000Z",
"updated": "2017-10-12T17:52:22.000Z",
"title": "Hard and Easy Instances of L-Tromino Tilings",
"authors": [
"Javier T. Akagi",
"Carlos F. Gaona",
"Fabricio Mendoza",
"Marcos Villagra"
],
"comment": "13 pages, 11 figures",
"categories": [
"cs.CC",
"cs.DS",
"math.CO"
],
"abstract": "In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we indentify restrictions to the problem where either it remains NP-complete or it has a polynomial time algorithm. First we show that an aztec diamond of order $n$ always has an L-tromino tiling if and only if $n(n+1)\\equiv 0\\mod 3$; if an aztec diamond has at least two defects or holes, however, the problem of deciding a tiling is NP-complete. Then we study tilings of arbitrary regions where only $180^\\circ$ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete, yet, if a region contains certain so-called \"forbidden polyominoes\" as subregions, then there exists a polynomial time algorithm for deciding a tiling.",
"revisions": [
{
"version": "v1",
"updated": "2017-10-12T17:52:22.000Z"
}
],
"analyses": {
"subjects": [
"68R05",
"F.2.2",
"G.2.1"
],
"keywords": [
"l-tromino tiling",
"polynomial time algorithm",
"aztec diamond",
"arbitrary region",
"study tilings"
],
"note": {
"typesetting": "TeX",
"pages": 13,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}