Wang tile

Wang tile

Wang tiles (or Wang dominoes), first proposed by mathematician Hao Wang in 1961, are a class of formal systems. They are modelled visually by equal-sized squares with a color on each edge which can be arranged side by side (on a regular square grid) so that abutting edges of adjacent tiles have the same color; the tiles cannot be rotated or reflected. The following shows an example set of 13 Wang tiles:

The basic question about sets of Wang tiles is proving whether they can tile the plane or not. This means that copies of the tiles can be arranged one by one to fill an infinite plane, without any grid position where no tile in the set can match the side colors of already laid out adjacent tiles.

In 1961, Wang presented an algorithm to take any finite set of tiles and decide whether they tiled the plane. In his purported proof of the correctness of the algorithm, he assumed that any set that could tile the plane would be able to tile the plane "periodically" (with a pattern that repeats, like standard wallpaper).

However, in 1966 Robert Berger proved Wang's conjecture was wrong. He presented a set of Wang tiles that could only tile the plane "aperiodically". This meant it could fill the plane without holes, but the tiling couldn't be a simple repetition of a finite pattern. This is similar to a Penrose tiling, or the arrangement of atoms in a quasicrystal. Although Berger's original set contained 20,426 tiles, he hypothesized that smaller sets would work, including subsets of his set. In later years, increasingly smaller sets were found. For example, the set of 13 tiles given above is an aperiodic set published by Karel Culik, II, in 1996. It can tile the plane, but not periodically.

Wang's algorithm for determining whether a given set of tiles can tile the plane was not correct. In fact, "no such algorithm can exist". It is possible to translate any Turing machine into a set of Wang tiles, such that the Wang tiles can tile the plane if and only if the Turing machine will never halt. The halting problem is undecidable, therefore the Wang tiling problem is also uncomputable. In a sense, Wang tiles have computational power equivalent to that of a Turing machine.

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

Wang tiles can be generalized in various ways, all of which are also undecidable in the above sense. For example, "Wang cubes" are equal-sized cubes with colored faces and side colors can be matched on any polygonal tessellation. Culik and Kari have demonstrated aperiodic sets of Wang cubes. Winfree et al. have demonstrated the feasibility of creating molecular "tiles" made from DNA (deoxyribonucleic acid) that can act as Wang tiles. Mittal et. al have shown that these tiles can also be composed of peptide nucleic acid (PNA), a stable artificial mimic of DNA.

Wang tiles have recently become a popular tool for procedural synthesis of textures, heightfields, and other large and nonrepeating bidimensional data sets; a small set of precomputed or hand-made source tiles can be assembled very cheaply without too obvious repetitions and without periodicity.In this case, traditional aperiodic tilings would show their very regular structure; much less constrained sets that guarantee at least two tile choices for any two given side colors are common because tileability is easily ensured and each tile can be selected pseudorandomly.Important papers about this new application include:
* Jos Stam (1997), [http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/R046.pdf "Aperiodic Texture Mapping"] introduces the idea of using Wang tiles for texture variation, with a deterministic substitution system.
* Michael F. Cohen, Jonathan Shade, Stefan Hiller, Oliver Deussen (2003), [http://research.microsoft.com/~cohen/WangFinal.pdf "Wang Tiles for Image and Texture Generation"] introduces stochastic tiling and is very popular.
* Li-Yi Wei (2004), [http://graphics.stanford.edu/papers/tile_mapping_gh2004/ "Tile-Based Texture Mapping on Graphics Hardware"] applies Wang Tiles for real-time texturing on a GPU
* Johannes Kopf, Daniel Cohen-Or, Oliver Deussen, Dani Lischinski (2006), [http://johanneskopf.de/publications/blue_noise "Recursive Wang Tiles for Real-Time Blue Noise"] shows advanced applications.

The short story "Wang's Carpets", later expanded to the novel Diaspora, by Greg Egan, postulates a universe, complete with resident organisms and intelligent beings, embodied as Wang tiles implemented by patterns of complex molecules.

ee also

*Tessellation

References

* Wang, Hao (January 1961). "Proving theorems by pattern recognition—II", "Bell System Tech. Journal" 40(1):1–41. (Wang proposes his tiles, and hypothesizes there are no aperiodic sets).
* Wang, H. (November 1965). "Games, logic and computers" in "Scientific American", pp. 98-106. (Presents them for a popular audience)
* Berger, R. (1966). "The undecidability of the domino problem", "Memoirs Amer. Math. Soc." 66(1966). (Coins the term "Wang tiles", and demonstrates the first aperiodic set of them).
* Cohen, M. F., Shade, J., Hiller, S., and Deussen, O. 2003. "Wang Tiles for image and texture generation", In ACM SIGGRAPH 2003 Papers (San Diego, California, July 27 - 31, 2003). SIGGRAPH '03. ACM Press, New York, NY, 287-294.
* Culik, K. (1996). "An aperiodic set of 13 Wang tiles", "Discrete Mathematics" 160, 245-251. (Showed an aperiodic set of 13 tiles with 5 colors).
* Kari, J. (1996). "A small aperiodic set of Wang tiles", "Discrete Mathematics" 160, 259-264.
* Culik, K., and J. Kari (1995). "An aperiodic set of Wang cubes", "Journal of Universal Computer Science" 1, 675-686 (1995).
* Winfree, E., Liu, F., Wenzler, L.A., and Seeman, N.C. (1998). “Design and Self-Assembly of Two-Dimensional DNA Crystals, Nature 394, 539-544.
* Lukeman, P., Seeman, N. and Mittal, A (2002). “Hybrid PNA/DNA Nanosystems.” In 1st International Conference on Nanoscale/Molecular Mechanics (N-M2-I), Outrigger Wailea Resort, Maui, Hawaii.

External links

* [http://www.uwgb.edu/dutchs/symmetry/aperiod.htm Steven Dutch's page including many pictures of aperiodic tilings]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Hao Wang (academic) — Infobox Scientist name = Hao Wang image width = caption = birth date = birth date|1921|5|20 birth place = Jinan, Shandong, China death date = death date|1995|5|13 death place = USA residence = citizenship = nationality = ethnicity = field =… …   Wikipedia

  • Greg Egan — Infobox Writer name = Greg Egan caption = pseudonym = birthdate = birth date and age|1961|8|20|df=y birthplace = Perth, Western Australia deathdate = deathplace = occupation = Writer, former Programmer nationality = Australian period = 1990s… …   Wikipedia

  • List of mathematics articles (W) — NOTOC Wad Wadge hierarchy Wagstaff prime Wald test Wald Wolfowitz runs test Wald s equation Waldhausen category Wall Sun Sun prime Wallenius noncentral hypergeometric distribution Wallis product Wallman compactification Wallpaper group Walrasian… …   Wikipedia

  • List of undecidable problems — In computability theory, an undecidable problem is a problem whose language is not a recursive set. More informally, such problems cannot be solved in general by computers; see decidability. This is a list of undecidable problems. Note that there …   Wikipedia

  • Undecidable problem — In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct an algorithm that leads to a yes or no answer the problem is not decidable.A decision problem is any …   Wikipedia

  • Recursive languages and sets — This article is a temporary experiment to see whether it is feasible and desirable to merge the articles Recursive set, Recursive language, Decidable language, Decidable problem and Undecidable problem. Input on how best to do this is very much… …   Wikipedia

  • 13 (number) — Number|number = 13 range = 10s cardinal = thirteen ordinal = th ordinal text = numeral = tredecimal factorization = prime prime = divisor = 1, 13 roman = XIII unicode = greek prefix = latin prefix = bin = 1101 oct = 15 duo = 11 hex = D misc =:… …   Wikipedia

  • Cellular automaton — A cellular automaton (plural: cellular automata) is a discrete model studied in computability theory, mathematics, theoretical biology and microstructure modeling. It consists of a regular grid of cells , each in one of a finite number of states …   Wikipedia

  • List of geometry topics — This is list of geometry topics, by Wikipedia page.*Geometric shape covers standard terms for plane shapes *List of mathematical shapes covers all dimensions *List of differential geometry topics *List of geometers *See also list of curves, list… …   Wikipedia

  • List of computability and complexity topics — This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computational complexity theory deals with how hard… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”