Tiling simply connected regions with rectangles

DOI10.1016/J.JCTA.2013.06.008MaRDI QIDQ2349205zbMATH OpenOpenAlexFDO

Authors Igor Pak, Jed Yang

Publication date 19 June 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.2796

zbMATH Keywords

\#P-completenessNP-completenessrectanglestiling

Mathematics Subject Classification ID

Combinatorial aspects of tessellation and tiling problems (05B45) Tilings in (2) dimensions (aspects of discrete geometry) (52C20)

Abstract: In [BNRR], it was shown that tiling of general regions with two rectangles is NP-complete, except for a few trivial special cases. In a different direction, R'emila showed that for simply connected regions by two rectangles, the tileability can be solved in quadratic time (in the area). We prove that there is a finite set of at most 10^6 rectangles for which the tileability problem of simply connected regions is NP-complete, closing the gap between positive and negative results in the field. We also prove that counting such rectangular tilings is #P-complete, a first result of this kind.

Recommendations

• Hard tiling problems with simple tiles
• Tiling figures of the plane with two bars
• Complexity of tiling a polygon with trominoes or bars
• scientific article; zbMATH DE number 417272
• Rectangular tileability and complementary tileability are undecidable

Cited in

(14)

• Tiling figures of the plane with two bars
• \(\mathsf{NP}\)-completeness of the game Kingdomino\(^\text{TM}\)
• Small polyomino packing
• Complexity of tiling a polygon with trominoes or bars
• Fast domino tileability
• The complexity of generalized domino tilings
• A PTAS for the square tiling problem
• Generalized dominoes tiling's Markov chain mixes fast
• Hard tiling problems with simple tiles
• Tiling with Squares and Packing Dominos in Polynomial Time
• Optimal deterministic controller synthesis from steady-state distributions
• Computational complexity of counting coincidences
• Partial decidability protocol for the Wang tiling problem from statistical mechanics and chaotic mapping
• Rectangular tileability and complementary tileability are undecidable

This page was built for publication: Tiling simply connected regions with rectangles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2349205)