Enumerating Cube Tilings

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

Research output: Contribution to journalArticle

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 languageEnglish
Pages (from-to)1112-1122
Number of pages11
JournalDiscrete and Computational Geometry
Volume50
Issue number4
DOIs
Publication statusPublished - 2013
Externally publishedYes

Fingerprint

Tiling
Regular hexahedron
Isomorphism Classes
Augmentation
Hypercube
n-dimensional
Pairwise
Cover
Integer

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

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

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 journalArticle

Mathew, KA, Östergård, PRJ & Popa, A 2013, 'Enumerating Cube Tilings', Discrete and Computational Geometry, vol. 50, no. 4, pp. 1112-1122. https://doi.org/10.1007/s00454-013-9547-4
Mathew, K. Ashik ; Östergård, Patric R J ; Popa, Alexandru. / Enumerating Cube Tilings. In: Discrete and Computational Geometry. 2013 ; Vol. 50, No. 4. pp. 1112-1122.
@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",
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

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 -