Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is a mathematical question raised from engineering and physics:

Is there some established mathematical approach in filling a physical lattice with some colored basis (black and white here)? For example, a triangular lattice can be filled with basis to getfilling

While enter image description here alone cannot give any filled colored graph. Is there any general systematic mathematical approach in solving this problem?

share|improve this question
It is overwhelmingly likely that the answer is "no" because the much-related problem of deciding whether a set of tiles can tile the plane is undecidable (google "Wang tiles"). An appropriate gadget should reduce the tiling question to your problem, showing that your problem is undecidable as well. –  Boris Bukh Nov 8 '13 at 21:29
"Undecidable" implies there is no general approach, but perhaps the author would settle for techniques that may work in various instances. Anyone? –  Gerry Myerson Nov 8 '13 at 22:50
Cross-posted at math.stackexchange.com/q/557240/18398 –  Joel Reyes Noche Nov 9 '13 at 0:35
@user40780, please do not simultaneously cross-post the same question across different StackExchange sites. This is frowned upon because it leads to duplication of effort. –  Joel Reyes Noche Nov 9 '13 at 0:38
@user40780, two days ago, the moderator Qmechanic already asked you not to cross-post at different StackExchange sites. I recommend that you follow their advice. –  Joel Reyes Noche Nov 9 '13 at 0:47
show 1 more comment

1 Answer

up vote 6 down vote accepted

The fact that Wang's procedure cannot theoretically work for arbitrary large tile sets does not render it useless for practical purposes.

This is from the Wikipedia web page on Wang tiles.

Here is an algorithm for special cases that may (not certain) apply to your situation ($|T|=4$). $T$ is a subset of $\mathbb{Z}^2$.

Abstract. ... Here we present two algorithms, one for the case when $|T|$ is prime, and another for the case when $|T|=4$ ...

Szegedy, Mario. "Algorithms to tile the infinite grid with finite clusters." Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on. IEEE, 1998. (IEEE link)

And finally, a bit off the beaten path, but very interesting:

Abel, Zachary, Nadia Benbernou, Mirela Damian, Erik D. Demaine, Martin L. Demaine, Robin Flatland, Scott D. Kominers, and Robert Schwelle. "Shape replication through self-assembly and RNase enzymes." In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1045-1064. Society for Industrial and Applied Mathematics, 2010. (ACM link):

share|improve this answer
Calling the link "Princeton webpage" because it is a copy of a Wikipedia page hosted by a Princeton grad student is misleading. I suggest changing link and the citation. –  Boris Bukh Nov 9 '13 at 1:25
@BorisBukh: Thank you, Boris---I didn't notice that it was a copy of a Wikipedia page! Corrected now. –  Joseph O'Rourke Nov 9 '13 at 1:45
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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