Cardiff University | Prifysgol Caerdydd ORCA
Online Research @ Cardiff 
WelshClear Cookie - decide language by browser settings

Hard and easy instances of L-Tromino tilings

Akagi, Javier T., Gaona, Carlos F., Mendoza, Fabricio, Saikia, Manjil and Villagra, Marcos 2018. Hard and easy instances of L-Tromino tilings. Presented at: International Workshop on Algorithms and Computation, Guwahati, India, 27 Feb - 2 Mar 2019. WALCOM: Algorithms and Computation. Springer Verlag, pp. 82-95. 10.1007/978-3-030-10564-8_7

[img]
Preview
PDF - Accepted Post-Print Version
Download (306kB) | Preview

Abstract

In this work we study tilings of regions in the square lattice with L-shaped trominoes. Deciding the existence of a tiling with L-trominoes for an arbitrary region in general is NP-complete, nonetheless, we identify restrictions to the problem where it either remains NP-complete or has a polynomial time algorithm. First, we characterize the possibility of when an Aztec rectangle has an L-tromino tiling, and hence also an Aztec diamond; if an Aztec rectangle has an unknown number of defects or holes, however, the problem of deciding a tiling is NP-complete. Then, we study tilings of arbitrary regions where only 180∘ rotations of L-trominoes are available. For this particular case we show that deciding the existence of a tiling remains NP-complete; yet, if a region does not contain so-called “forbidden polyominoes” as subregions, then there exists a polynomial time algorithm for deciding a tiling.

Item Type: Conference or Workshop Item (Paper)
Date Type: Published Online
Status: Published
Schools: Mathematics
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Publisher: Springer Verlag
ISBN: 978-3-030-10563-1
ISSN: 0302-9743
Date of First Compliant Deposit: 24 February 2020
Last Modified: 26 Feb 2020 15:00
URI: http://orca.cf.ac.uk/id/eprint/129923

Citation Data

Cited 1 time in Scopus. View in Scopus. Powered By Scopus® Data

Actions (repository staff only)

Edit Item Edit Item

Downloads

Downloads per month over past year

View more statistics