ワンタイル

1961年にHao Wangが、与えられたタイルの集合で平面を敷き詰められるかを調べるために提案した。いわゆるドミノ問題である。Wangは、平面を敷き詰められる集合は必ず周期的に敷き詰めると予想したが、1966年にRobert Bergerが非周期的な集合で反証し、この問題は一般には決定不能だと分かった。数学としては見事だが、グラフィックスで実を結ぶのはずっと後のことになる。

2003年にCohenらは、辺が一致する少数のタイルを並べるだけで、目に見える繰り返しのない巨大なテクスチャや地形を、低い実行時コストで作れることを示した。発想はオートタイリングや、波動関数崩壊が一般化した一致制約に近く、タイルマップにもそのまま収まる。