Back to Search
Start Over
Hard Tiling Problems with Simple Tiles
- Publication Year :
- 2000
- Publisher :
- arXiv, 2000.
-
Abstract
- It is well-known that the question of whether a given finite region can be tiled with a given set of tiles is NP-complete. We show that the same is true for the right tromino and square tetromino on the square lattice, or for the right tromino alone. In the process, we show that Monotone 1-in-3 Satisfiability is NP-complete for planar cubic graphs. In higher dimensions, we show NP-completeness for the domino and straight tromino for general regions on the cubic lattice, and for simply-connected regions on the four-dimensional hypercubic lattice.
- Subjects :
- Discrete mathematics
Lattice (group)
Square lattice
Square (algebra)
Satisfiability
Theoretical Computer Science
Combinatorics
Monotone polygon
Computational Theory and Mathematics
Simply connected space
Tromino
FOS: Mathematics
Discrete Mathematics and Combinatorics
Cubic graph
Mathematics - Combinatorics
Geometry and Topology
Combinatorics (math.CO)
Mathematics
Subjects
Details
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....380537e44046855ab0198c185e5a044f
- Full Text :
- https://doi.org/10.48550/arxiv.math/0003039