4
$\begingroup$

Non-overlapping tilings of regions is a well-studied topic. I wonder if the following variant has been considered:

A tile can be partitioned into several regions, where such regions from different tiles may overlap, according to some set of rules, similar (but not the same) as pieces of a puzzle.

A natural example would be to consider all areas covered by industrial machine as a tile, but not all parts of the machine are active at the same time. Thus, not all regions around the machine are occupied at the same time, which allows one to put several such machines closer together, as long as two "active" regions do not overlap.

From a mathematical point if view, the following is a natural question: Given a finite set of rectangular tiles, each with rectangular regions, and a set of rules that determine how the regions may overlap, together with some larger region of the plane, what is the complexity to determine if the tiles can fit inside this large region without violating the rules?

This sounds like an NP-complete problem.

$\endgroup$
  • 1
    $\begingroup$ This sounds like it should reduce to a polynomially larger tiling problem with "overlap" tiles and "tile fragments". Have you consider such a reduction? Gerhard "Let's Break Apart The Problem" Paseman, 2015.01.26 $\endgroup$ – Gerhard Paseman Jan 26 '15 at 22:24
  • $\begingroup$ Sidenote: Petra Gummelt described a decagonal "tile" that can cover space with certian overlap restrictions but not periodically. gregegan.customer.netspace.net.au/APPLETS/06/06.html $\endgroup$ – Yoav Kallus Jan 26 '15 at 22:58
7
$\begingroup$

This is a very special case, but ...

Let the tiles be $2 \times 2$ squares, tetrominoes, with the subregion of one $1 \times 1$ fourth of the square permitted to overlap. So the squares could become, effectively, right trominoes if one-quarter (but not more) overlaps:


          CrisMooreFig1
(Here "overlap" means overlap with another tile as well as "overlapping" with the region exterior to that desired to be covered.)

Then the paper,

Moore, Cristopher, and John Michael Robson. "Hard tiling problems with simple tiles." Discrete & Computational Geometry 26.4 (2001): 573-590. (arXiv link).

establishes that tiling a given finite region of the square lattice with these two tiles is NP-complete. Reinterpreting in terms of allowed overlap appears to show this specific version of your general problem is NP-complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Ah, I suspected that there was such an example! Thank you very much for this! $\endgroup$ – Per Alexandersson Jan 27 '15 at 0:54
  • 1
    $\begingroup$ Thanks, but allowing "overlap" with the exterior of the region is unnatural. So there is still more to do to entirely settle your question. $\endgroup$ – Joseph O'Rourke Jan 27 '15 at 12:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.