Abstract
Cube tilings formed by n-dimensional 4ℤn-periodic hypercubes with side 2 and integer coordinates are considered here. By representing the problem of finding such cube tilings within the framework of exact cover and using canonical augmentation, pairwise nonisomorphic 5-dimensional cube tilings are exhaustively enumerated in a constructive manner. There are 899,710,227 isomorphism classes of such tilings, and the total number of tilings is 638,560,878,292,512. It is further shown that starting from a 5-dimensional cube tiling and using a sequence of switching operations, it is possible to generate any other cube tiling.
| Original language | English |
|---|---|
| Pages (from-to) | 1112-1122 |
| Number of pages | 11 |
| Journal | Discrete and Computational Geometry |
| Volume | 50 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2013 |
| Externally published | Yes |
Fingerprint
Keywords
- Classification
- Cube tilings
- Exact cover
- Switching graph
ASJC Scopus subject areas
- Theoretical Computer Science
- Computational Theory and Mathematics
- Discrete Mathematics and Combinatorics
- Geometry and Topology
Cite this
Enumerating Cube Tilings. / Mathew, K. Ashik; Östergård, Patric R J; Popa, Alexandru.
In: Discrete and Computational Geometry, Vol. 50, No. 4, 2013, p. 1112-1122.Research output: Contribution to journal › Article
}
TY - JOUR
T1 - Enumerating Cube Tilings
AU - Mathew, K. Ashik
AU - Östergård, Patric R J
AU - Popa, Alexandru
PY - 2013
Y1 - 2013
N2 - Cube tilings formed by n-dimensional 4ℤn-periodic hypercubes with side 2 and integer coordinates are considered here. By representing the problem of finding such cube tilings within the framework of exact cover and using canonical augmentation, pairwise nonisomorphic 5-dimensional cube tilings are exhaustively enumerated in a constructive manner. There are 899,710,227 isomorphism classes of such tilings, and the total number of tilings is 638,560,878,292,512. It is further shown that starting from a 5-dimensional cube tiling and using a sequence of switching operations, it is possible to generate any other cube tiling.
AB - Cube tilings formed by n-dimensional 4ℤn-periodic hypercubes with side 2 and integer coordinates are considered here. By representing the problem of finding such cube tilings within the framework of exact cover and using canonical augmentation, pairwise nonisomorphic 5-dimensional cube tilings are exhaustively enumerated in a constructive manner. There are 899,710,227 isomorphism classes of such tilings, and the total number of tilings is 638,560,878,292,512. It is further shown that starting from a 5-dimensional cube tiling and using a sequence of switching operations, it is possible to generate any other cube tiling.
KW - Classification
KW - Cube tilings
KW - Exact cover
KW - Switching graph
UR - http://www.scopus.com/inward/record.url?scp=84890394508&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84890394508&partnerID=8YFLogxK
U2 - 10.1007/s00454-013-9547-4
DO - 10.1007/s00454-013-9547-4
M3 - Article
VL - 50
SP - 1112
EP - 1122
JO - Discrete and Computational Geometry
JF - Discrete and Computational Geometry
SN - 0179-5376
IS - 4
ER -