5
$\begingroup$

As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a more practical aspect. Say, if the program accidentally ("or systematically") find some "periodic structure", then it stops and tells me there exists periodic pattern. If during running, it enumerates all the use of tile and finds that it simply cannot tile the plane, then it tell me this set of tiles cannot tile the plane. Even if the program didn't stop, then after running some steps, it returns me a few most ordered patterns that that could "possibly tile the plane".

For practical purpose, I simply assume if the tessellation are up to some size (maybe 1000*1000) then I say "it could tile the plane practically".

So my most interested question is: is there any established programs or algorithms that "try" to help me analyze a set of tile even if it might not halt ("but I could define some imposed halting condition").

For context why I am interested in this problem, here's the links:

coloring in lattice

Reference for Wang Tile

Periodic Tiling of Wang tile

Cross-posted to:

https://cs.stackexchange.com/questions/21502/computational-approach-deciding-whether-a-set-of-wang-tile-could-tile-the-space

$\endgroup$
4
  • 2
    $\begingroup$ Crossposted on cs.SE. $\endgroup$
    – Raphael
    Feb 10, 2014 at 21:54
  • 5
    $\begingroup$ Dear @user40780, please do not post questions simultaneously to multiple sites. It leads to unnecessary duplication of effort, and is commonly frowned upon by the MathOverflow community and others. Please post to one site and wait at least a few days for an answer. $\endgroup$ Feb 10, 2014 at 22:56
  • 1
    $\begingroup$ This is actually a more practical problem. I wish to have it solved.... $\endgroup$
    – user40780
    Feb 14, 2014 at 18:38
  • 1
    $\begingroup$ You may be interested to explore this book: Wang Tiles in Computer Graphics, to see if it can give insights to your problem. $\endgroup$ Feb 15, 2014 at 1:09

1 Answer 1

4
+50
$\begingroup$

There are a few theory papers tackling issue involved in Wang Tile:

Tiling groups for Wang tiles by Cristopher Moore, Ivan Rapaport, Eric Remila

Also recent development considering finite cases of Wang tile is considered here.

https://arxiv.org/abs/1305.2796

https://arxiv.org/abs/1212.3380

There are not yet exact answers to this problem as far as I know, but hope this helps....

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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