Back to search

University of Victoria (Canada)

Monomino-Domino Tatami Coverings

Abstract

dc:description.abstract

We present several new results on the combinatorial properties of a locally restricted version of monomino-domino coverings of rectilinear regions. These are monomino-domino tatami coverings, and the restriction is that no four tiles may meet at any point. The global structure that the tatami restriction induces has numerous implications, and provides a powerful tool for solving enumeration problems on tatami coverings. Among these we address the enumeration of coverings of rectangles, with various parameters, and we develop algorithms for exhaustive generation of coverings, in constant amortised time per covering. We also con- sider computational complexity on two fronts; firstly, the structure shows that the space required to store a covering of the rectangle is linear in its longest dimension, and secondly, it is NP-complete to decide whether an arbitrary polyomino can be tatami-covered only with dominoes.

Degree

thesis:*
Level thesis:degree_level
Doctor of Philosophy Ph.D.
Department thesis:degree_department
Department of Computer Science
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Erickson, Alejandro
Advisor dc:contributor.supervisor
  • Ruskey, Frank

Subjects

dc:subject × 15

Rights

dc:rights
Statement dc:rights
  • Available to the World Wide Web
Language dc:language.iso
en, English

Identifiers

dc:identifier.*
Dc Identifier Citation
Alejandro Erickson and Mark Schurch. Monomer-dimer tatami tilings of square regions. Journal of Discrete Algorithms, 16(0):258–269, October 2012.
Alejandro Erickson and Mark Schurch. Enumerating tatami mat arrange- ments of square grids. In International Workshop on Combinatorial Algorithms (IWOCA), volume 7056 of LNCS, pages 223–235. Springer Berlin / Heidel- berg, January 2011.
Alejandro Erickson, Frank Ruskey, Mark Schurch, and Jennifer Woodcock. Monomer-dimer tatami tilings of rectangular regions. The Electronic Journal of Combinatorics, 18(1):24, 2011.
Alejandro Erickson and Frank Ruskey. Domino Tatami Covering is NP- complete. In The International Workshop on Combinatorial Algorithms (IWOCA), July 2013. 10 pages, to appear in Lecture Notes in Computer Science (LNCS). http://arxiv.org/abs/1305.6669.
Alejandro Erickson. TatamiMaker: A combinatorially rich mechanical game board. In Bridges, June 2013. 8 pages. http://arxiv.org/abs/1301.5969.

Chain of custody

source
Harvested from
University of Victoria (Canada)
Base URL
dspace.library.uvic.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Erickson, Alejandro. Monomino-Domino Tatami Coverings. Doctor of Philosophy Ph.D. thesis, 2013. http://hdl.handle.net/1828/4902