Wang-betegeling
Een wang-betegeling is een betegeling van het tweedimensionale vlak met zogenaamde wang-tegels of wang-domino's. Dit zijn identieke vierkanten die verdeeld zijn in vier driehoekige gedeelten door hun twee diagonalen. Elke driehoek heeft een bepaalde kleur. De betegeling gebeurt met een eindige verzameling van deze tegels, elk met een verschillende keuze van kleuren. De betegeling gebeurt in een rechthoekig patroon en zodanig dat tegels die elkaar raken dat moeten doen met dezelfde kleur. De tegels mogen niet gedraaid of gespiegeld worden. Elke tegel uit de verzameling mag een eindig of oneindig aantal keren gebruikt worden. Deze betegeling werd in 1961 bedacht door de wiskundige Hao Wang.
Dit is een voorbeeldverzameling van 13 wang-tegels:
Beslissingsprobleem[bewerken | brontekst bewerken]
De vraag stelt zich hierbij, of het met een gegeven eindige verzameling van wangtegels mogelijk is om het oneindige vlak te betegelen. Wang publiceerde voor dit beslissingsprobleem in 1961 een algoritme. In zijn bewijs van de correctheid daarvan nam hij aan, dat elke verzameling die in staat is om het vlak te betegelen, dat met een periodieke betegeling zou doen. Dit wil zeggen dat het oneindige vlak betegeld kan worden met een eindige, zich periodiek herhalende groepering van wang-tegels.[1]
In 1965 bewees Robert Berger echter, dat deze aanname van Wang verkeerd was.[2] Berger, die de term "wang-tegels" introduceerde, toonde aan dat er een verzameling van wang-tegels bestaat waarmee het vlak enkel aperiodiek betegeld kan worden, dus zonder een zich periodiek herhalende groep. Het algoritme van Wang was dus verkeerd.
Elke eindige verzameling van wangtegels kan beschouwd worden als een model voor een turingmachine, waarbij geldt dat de wangtegels het vlak slechts dan betegelen als de turingmachine niet stopt. Nu is het bekend dat het stopprobleem een onbeslisbaar probleem is, en dus is het beslissingsprobleem van de wangbetegeling dat ook: er bestaat met andere woorden geen algoritme om te besluiten of het vlak betegeld kan worden met een gegeven verzameling van wangtegels.
De eerste aperiodieke verzameling die Robert Berger voorstelde bestond uit 20.526 verschillende tegels. Hij vermoedde wel dat er kleinere aperiodieke verzamelingen moesten bestaan. Die zijn ook gevonden: de set van dertien tegels in vijf kleuren die hierboven is afgebeeld is een aperiodieke verzameling, die door Karel Culik werd gepubliceerd.[3]
Uitbreiding naar drie dimensies[bewerken | brontekst bewerken]
Het principe van de wang-betegeling kan men in de driedimensionale ruimte toepassen met "wang-kubussen", even grote kubussen waarvan elke zijde een bepaalde kleur heeft. Die worden zodanig in de ruimte gestapeld dat kubussen elkaar steeds met dezelfde kleur moeten raken. Hiervoor zijn ook verzamelingen van wang-kubussen bekend waarmee de ruimte enkel aperiodiek gevuld kan worden.[4]
Toepassingen[bewerken | brontekst bewerken]
Wang-tegels en -kubussen hebben toepassing gevonden in 2D- en 3D-computergraphics voor zaken als snelle texture mapping.[5][6][7]
Zie ook[bewerken | brontekst bewerken]
Externe links[bewerken | brontekst bewerken]
- (en) Website van Steven Dutchs over aperiodische betegelingen
- (en) Wang Tiles (paper waarin de onbeslisbaarheid van wang-betegeling wordt aangetoond)
Bronnen, noten en/of referenties
|