Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAn aperiodic set of 11 Wang tiles
248
0
0.0
(
0
)
Added by
Michael Rao
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Authors
Emmanuel Jeandel
Ask ChatGPT about the research
No Arabic abstract
We present a new aperiodic tileset containing 11 Wang tiles on 4 colors, and we show that this tileset is minimal, in the sense that no Wang set with either fewer than 11 tiles or fewer than 4 colors is aperiodic. This gives a definitive answer to the problem raised by Wang in 1961.
rate research
Read More
We define a Wang tile set $mathcal{U}$ of cardinality 19 and show that the set $Omega_mathcal{U}$ of all valid Wang tilings $mathbb{Z}^2tomathcal{U}$ is self-similar, aperiodic and is a minimal subshift of $mathcal{U}^{mathbb{Z}^2}$. Thus $mathcal{U}$ is the second smallest self-similar aperiodic Wang tile set known after Ammanns set of 16 Wang tiles. The proof is based on the unique composition property. We prove the existence of an expansive, primitive and recognizable $2$-dimensional morphism $omega:Omega_mathcal{U}toOmega_mathcal{U}$ that is onto up to a shift. The proof of recognizability is done in two steps using at each step the same criteria (the existence of marker tiles) for proving the existence of a recognizable one-dimensional substitution that sends each tile either on a single tile or on a domino of two tiles.
Microstructural geometry plays a critical role in the response of heterogeneous materials. Consequently, methods for generating microstructural samples are increasingly crucial to advanced numerical analyses. We extend Sonon et al.s unified framework, developed originally for generating particulate and foam-like microstructural geometries of Periodic Unit Cells, to non-periodic microstructural representations based on the formalism of Wang tiles. This formalism has been recently proposed in order to generalize the Periodic Unit Cell approach, enabling a fast synthesis of arbitrarily large, stochastic microstructural samples from a handful of domains with predefined compatibility constraints. However, a robust procedure capable of designing complex, three-dimensional, foam-like and cellular morphologies of Wang tiles has not yet been proposed. This contribution fills the gap by significantly broadening the applicability of the tiling concept. Since the original Sonon et al.s framework builds on a random sequential addition of particles enhanced with an implicit representation of particle boundaries by the level-set field, we first devise an analysis based on a connectivity graph of a tile set, resolving the question where a particle should be copied when it intersects a tile boundary. Next, we introduce several modifications to the original algorithm that are necessary to ensure microstructural compatibility in the generalized periodicity setting of Wang tiles. Having established a universal procedure for generating tile morphologies, we compare strictly aperiodic and stochastic sets with the same cardinality in terms of reducing the artificial periodicity in reconstructed microstructural samples. We demonstrate the superiority of the vertex-defined tile sets for two-dimensional problems and illustrate the capabilities of the algorithm with two- and three-dimensional examples.
This investigation completely classifies the spatial chaos problem in plane edge coloring (Wang tiles) with two symbols. For a set of Wang tiles $mathcal{B}$, spatial chaos occurs when the spatial entropy $h(mathcal{B})$ is positive. $mathcal{B}$ is called a minimal cycle generator if $mathcal{P}(mathcal{B}) eqemptyset$ and $mathcal{P}(mathcal{B})=emptyset$ whenever $mathcal{B}subsetneqq mathcal{B}$, where $mathcal{P}(mathcal{B})$ is the set of all periodic patterns on $mathbb{Z}^{2}$ generated by $mathcal{B}$. Given a set of Wang tiles $mathcal{B}$, write $mathcal{B}=C_{1}cup C_{2} cupcdots cup C_{k} cup N$, where $C_{j}$, $1leq jleq k$, are minimal cycle generators and $mathcal{B}$ contains no minimal cycle generator except those contained in $C_{1}cup C_{2} cupcdots cup C_{k}$. Then, the positivity of spatial entropy $h(mathcal{B})$ is completely determined by $C_{1}cup C_{2} cupcdots cup C_{k}$. Furthermore, there are 39 equivalent classes of marginal positive-entropy (MPE) sets of Wang tiles and 18 equivalent classes of saturated zero-entropy (SZE) sets of Wang tiles. For a set of Wang tiles $mathcal{B}$, $h(mathcal{B})$ is positive if and only if $mathcal{B}$ contains an MPE set, and $h(mathcal{B})$ is zero if and only if $mathcal{B}$ is a subset of an SZE set.
The Wang tiling is a classical problem in combinatorics. A major theoretical question is to find a (small) set of tiles which tiles the plane only aperiodically. In this case, resulting tilings are rather restrictive. On the other hand, Wang tiles are used as a tool to generate textures and patterns in computer graphics. In these applications, a set of tiles is normally chosen so that it tiles the plane or its sub-regions easily in many different ways. With computer graphics applications in mind, we introduce a class of such tileset, which we call sequentially permissive tilesets, and consider tiling problems with constrained boundary. We apply our methodology to a special set of Wang tiles, called Brick Wang tiles, introduced by Derouet-Jourdan et al. in 2015 to model wall patterns. We generalise their result by providing a linear algorithm to decide and solve the tiling problem for arbitrary planar regions with holes.
Motivated by the study of Fibonacci-like Wang shifts, we define a numeration system for $mathbb{Z}$ and $mathbb{Z}^2$ based on the binary alphabet ${0,1}$. We introduce a set of 16 Wang tiles that admits a valid tiling of the plane described by a deterministic finite automaton taking as input the representation of a position $(m,n)inmathbb{Z}^2$ and outputting a Wang tile.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
