Detecting hierarchy in tiling dynamical systems via derived Voronoi tessellations

Tilings of multidimensional Euclidean space can display hierarchy similar to that seen in sequences which are limit points of substitutions. Intuitively speaking, the tiles in a hierarchical tiling can be grouped together to form larger tiles so that the resulting tiling made from the larger tiles is "isomorphic" to the original tiling. Three types of hierarchical tilings are studied in this work: self-similar tilings, pseudo-self-similar tilings, and combinatorially substitutive tilings. Self-similarity is a very rigid geometric condition, while only combinatorial requirements must be satisfied for a tiling to display combinatorial hierarchy.; It is already an important question in the symbolic case whether or not a sequence is a substitution sequence. A characterization of substitution sequences has been obtained by F. Durand in terms of "derived sequences" (recodings in terms of reappearances of any initial block). Durand showed that a sequence is substitutive primitive if and only if the set of its derived sequences is finite. In connection with Durand's work, we define the notion of a "derived Voronoi tiling". Any tiling has associated to it a set of derived Voronoi tilings which may include an infinite number of non-isomorphic tilings. We show that the set of derived Voronoi tilings which come from a self-similar tiling includes only a finite number of tilings up to similarity. Starting instead with an arbitrary tiling, we show that derived Voronoi tilings can be used to detect whether there is hierarchy present in its structure. If its set of derived Voronoi tilings is finite up to combinatorial isomorphism, we show that it is combinatorially substitutive. Moreover, if it has only a finite number of derived Voronoi tilings up to similarity, then it is a pseudo-self-similar tiling.