Return to search

Monomino-Domino Tatami Coverings

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. / Graduate / 0984 / 0405 / alejandro.erickson@gmail.com

Identiferoai:union.ndltd.org:uvic.ca/oai:dspace.library.uvic.ca:1828/4902
Date03 September 2013
CreatorsErickson, Alejandro
ContributorsRuskey, Frank
Source SetsUniversity of Victoria
LanguageEnglish, English
Detected LanguageEnglish
TypeThesis
RightsAvailable to the World Wide Web

Page generated in 0.0022 seconds