NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914951476543488 |
|---|---|
| author | Yang, Chao Zhang, Zhujun |
| author_facet | Yang, Chao Zhang, Zhujun |
| contents | The computational complexity of tiling finite simply connected regions with a fixed set of tiles is studied in this paper. We show that the problem of tiling simply connected regions with a fixed set of $23$ Wang tiles is NP-complete. As a consequence, the problem of tiling simply connected regions with a fixed set of $111$ rectangles is NP-complete. Our results improve that of Igor Pak and Jed Yang by using fewer numbers of tiles. Notably in the case of Wang tiles, the number has decreased by more than one third from $35$ to $23$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_01017 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles Yang, Chao Zhang, Zhujun Combinatorics Computational Complexity Metric Geometry The computational complexity of tiling finite simply connected regions with a fixed set of tiles is studied in this paper. We show that the problem of tiling simply connected regions with a fixed set of $23$ Wang tiles is NP-complete. As a consequence, the problem of tiling simply connected regions with a fixed set of $111$ rectangles is NP-complete. Our results improve that of Igor Pak and Jed Yang by using fewer numbers of tiles. Notably in the case of Wang tiles, the number has decreased by more than one third from $35$ to $23$. |
| title | NP-completeness of Tiling Finite Simply Connected Regions with a Fixed Set of Wang Tiles |
| topic | Combinatorics Computational Complexity Metric Geometry |
| url | https://arxiv.org/abs/2405.01017 |