Enumerating Cube Tilings

K. Ashik Mathew; Patric R.J. Östergård; Alexandru Popa

doi:10.1007/s00454-013-9547-4

Enumerating Cube Tilings

K. Ashik Mathew, Patric R.J. Östergård, Alexandru Popa

Department of Computer Science

Research output: Contribution to journal › Article

2 Citations (Scopus)

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	https://doi.org/10.1007/s00454-013-9547-4
Publication status	Published - Jan 1 2013

Fingerprint

Keywords

Classification
Cube tilings
Exact cover
Switching graph

ASJC Scopus subject areas

Theoretical Computer Science
Geometry and Topology
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Cite this

Mathew, K. A., Östergård, P. R. J., & Popa, A. (2013). Enumerating Cube Tilings. Discrete and Computational Geometry, 50(4), 1112-1122. https://doi.org/10.1007/s00454-013-9547-4

@article{e2a279dfc46b448c99a25119ec2e5ace,

title = "Enumerating Cube Tilings",

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.",

keywords = "Classification, Cube tilings, Exact cover, Switching graph",

author = "Mathew, {K. Ashik} and {\"O}sterg{\aa}rd, {Patric R.J.} and Alexandru Popa",

year = "2013",

month = jan

day = "1",

doi = "10.1007/s00454-013-9547-4",

language = "English",

volume = "50",

pages = "1112--1122",

journal = "Discrete and Computational Geometry",

issn = "0179-5376",

publisher = "Springer New York",

number = "4",

}

TY - JOUR

T1 - Enumerating Cube Tilings

AU - Mathew, K. Ashik

AU - Östergård, Patric R.J.

AU - Popa, Alexandru

PY - 2013/1/1

Y1 - 2013/1/1

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

AN - SCOPUS:84890394508

VL - 50

SP - 1112

EP - 1122

JO - Discrete and Computational Geometry

JF - Discrete and Computational Geometry

SN - 0179-5376

IS - 4

ER -

Access to Document

10.1007/s00454-013-9547-4