Finite subdivision rule

A subdivision rule takes a tiling of the plane by polygons and turns it into a new tiling by subdividing each polygon into smaller polygons. It is finite if there are only finitely many ways that every polygon can subdivide. Each way of subdividing a tile is called a tile type. Each tile type is represented by a label (usually a letter). Every tile type subdivides into smaller tile types. Each edge also gets subdivided according to finitely many edge types. Finite subdivision rules can only subdivide tilings that are made up of polygons labelled by tile types. Such tilings are called subdivision complexes for the subdivision rule. Given any subdivision complex for a subdivision rule, we can subdivide it over and over again to get a sequence of tilings. For instance, binary subdivision has one tile type and one edge type. All quadrilaterals are type A tiles. Since the only tile type is a quadrilateral, binary subdivision can only subdivide tilings made up of quadrilaterals. This means that the only subdivision complexes are tilings by quadrilaterals. The tiling can be regular, but doesn't have to be. The following example starts with a complex made of four quadrilaterals and subdivides it twice. ==Examples of finite subdivision rules==

Barycentric subdivision is an example of a subdivision rule with one edge type (that gets subdivided into two edges) and one tile type (a triangle that gets subdivided into 6 smaller triangles). Any triangulated surface is a barycentric subdivision complex. The Penrose tiling can be generated by a subdivision rule on a set of four tile types (the curved lines in the table below only help to show how the tiles fit together): Certain rational maps give rise to finite subdivision rules. This includes most Lattès maps. Every prime, non-split alternating knot or link complement has a subdivision rule, with some tiles that do not subdivide, corresponding to the boundary of the link complement. The subdivision rules show what the night sky would look like to someone living in a knot complement; because the universe wraps around itself (i.e. is not simply connected), an observer would see the visible universe repeat itself in an infinite pattern. The subdivision rule describes that pattern. The subdivision rule looks different for different geometries. This is a subdivision rule for the trefoil knot, which is not a hyperbolic knot: And this is the subdivision rule for the Borromean rings, which is hyperbolic: In each case, the subdivision rule would act on some tiling of a sphere (i.e. the night sky), but it is easier to just draw a small part of the night sky, corresponding to a single tile being repeatedly subdivided. This is what happens for the trefoil knot: And for the Borromean rings: ==In higher dimensions==

Subdivision rules can easily be generalized to other dimensions. For instance, barycentric subdivision is used in all dimensions. Also, binary subdivision can be generalized to other dimensions (where hypercubes get divided by every midplane), as used in certain proofs in higher-dimensional mathematical analysis such as for the Bolzano–Weierstrass theorem and Heine–Borel theorem. ==Rigorous definition==

A finite subdivision rule R consists of the following. • A finite 2-dimensional CW complex S_R, called the subdivision complex, with a fixed cell structure such that S_R is the union of its closed 2-cells. We assume that for each closed 2-cell \tilde{s} of S_R there is a CW structure s on a closed 2-disk such that s has at least two vertices, the vertices and edges of s are contained in \partial s, and the characteristic map \psi_s:s\rightarrow S_R which maps onto \tilde{s} restricts to a homeomorphism onto each open cell. • A finite two dimensional CW complex R(S_R), which is a subdivision of S_R. • A continuous cellular map \phi_R:R(S_R)\rightarrow S_R called the subdivision map, whose restriction to every open cell is a homeomorphism onto an open cell. Each CW complex s in the definition above (with its given characteristic map \psi_s) is called a tile type. An R-complex for a subdivision rule R is a 2-dimensional CW complex X which is the union of its closed 2-cells, together with a continuous cellular map f:X\rightarrow S_R whose restriction to each open cell is a homeomorphism. We can subdivide X into a complex R(X) by requiring that the induced map f:R(X)\rightarrow R(S_R) restricts to a homeomorphism onto each open cell. R(X) is again an R-complex with map \phi_R \circ f:R(X)\rightarrow S_R. Repeating this process produces a sequence of subdivided R-complexes R^n(X) with maps \phi_R^n\circ f:R^n(X)\rightarrow S_R. ==Quasi-isometry properties==

subdivision rule. Subdivision rules can be used to study the quasi-isometry properties of certain spaces. The quasi-isometry properties of the history graph can be studied using subdivision rules. For instance, the history graph is quasi-isometric to hyperbolic space exactly when the subdivision rule is "conformal", as described in the combinatorial Riemann mapping theorem. ==Applications==

Islamic Girih tiles in Islamic architecture are self-similar tilings that can be modeled with finite subdivision rules. Subdivision surfaces in computer graphics use subdivision rules to refine a surface to any given level of precision. These subdivision surfaces (such as the Catmull-Clark subdivision surface) take a polygon mesh (the kind used in 3D animated movies) and refine it to a mesh with more polygons by adding and shifting points according to different recursive formulas. Although many points get shifted in this process, each new mesh is combinatorially a subdivision of the old mesh (meaning that for every edge and vertex of the old mesh, one can identify a corresponding edge and vertex in the new one, plus several more edges and vertices). Subdivision rules were applied by to the study of large-scale growth patterns of biological organisms. They produced a mathematical growth model which demonstrated that some systems determined by simple finite subdivision rules can result in objects (in their example, a tree trunk) whose large-scale form oscillates wildly over time, even though the local subdivision laws remain the same. They also applied their model to the analysis of the growth patterns of rat tissue. They suggested that the "negatively curved" (or non-euclidean) nature of microscopic growth patterns of biological organisms is one of the key reasons why large-scale organisms do not look like crystals or polyhedral shapes but in fact in many cases resemble self-similar fractals. In particular, they suggested that such "negatively curved" local structure is manifested in the highly folded and highly connected nature of the brain and the lung tissue. ==Cannon's conjecture==

Cannon, Floyd, and Parry first studied finite subdivision rules as an attempt to prove the following conjecture: Here, a geometric action is a cocompact, properly discontinuous action by isometries. This conjecture was partially solved by Grigori Perelman in his proof of the geometrization conjecture, which states (in part) that any Gromov hyperbolic group that is a 3-manifold group must act geometrically on hyperbolic 3-space. However, it still remains to be shown that a Gromov hyperbolic group with a 2-sphere at infinity is a 3-manifold group. Cannon and Swenson showed that a hyperbolic group with a 2-sphere at infinity has an associated subdivision rule. If this subdivision rule is conformal in a certain sense, the group will be a 3-manifold group with the geometry of hyperbolic 3-space. ==Combinatorial Riemann mapping theorem==

Subdivision rules provide a sequence of tilings of a surface, and tilings offer an intuitive understanding of distance, length, and area (by assigning each tile a length and area of 1). In the limit, the distances that come from these tilings may converge in some sense to an analytic structure on the surface. The combinatorial Riemann mapping theorem gives necessary and sufficient conditions for this to occur. Its statement needs some background. A tiling T of a ring R (i.e., a closed annulus) gives two invariants, M_{\sup} (R, T) and m_{\inf} (R ,T), called approximate moduli. These are similar to the classical modulus of a ring. They are defined by the use of "weight functions". A weight function \rho assigns a non-negative number called a "weight" to each tile of T. Every path in R can be given a length, defined to be the sum of the weights of all tiles in the path. Define the height H(\rho) of R under \rho to be the infimum of the length of all possible paths connecting the inner boundary of R to the outer boundary. The circumference C(\rho) of R under \rho is the infimum of the length of all possible paths circling the ring (i.e., not nullhomotopic in R). The area A(\rho) of R under \rho is defined to be the sum of the squares of all weights in R. Invariant under scaling of the metric, they can be defined as: \begin{align} M_{\sup} (R,T) &= \sup \frac{H(\rho)^2}{A(\rho)}, \\ m_{\inf} (R,T) &= \inf \frac{A(\rho)}{C(\rho)^2}. \end{align} A sequence T_1,T_2,\ldots of tilings is conformal (K) if mesh approaches 0 and: • For each ring R, the approximate moduli M_{\sup}(R,T_i) and m_{\inf}(R,T_i), for all i sufficiently large, lie in a single interval of the form [r,Kr]; and • Given a point x in the surface, a neighborhood N of x, and an integer I, there is a ring R in N\smallsetminus\{x\} separating x from the complement of N, such that for all large i the approximate moduli of R are all greater than I. Statement of theorem If a sequence T_1,T_2,\ldots of tilings of a surface is conformal (K) in the above sense, then there is a conformal structure on the surface and a constant K' depending only on K in which the classical moduli and approximate moduli (from T_i for i sufficiently large) of any given annulus are K'-comparable, meaning that they lie in a single interval [r,K'r]. Consequences The combinatorial Riemann mapping theorem implies that a group G acts geometrically on \mathbb{H}^3 if and only if it is Gromov hyperbolic, it has a sphere at infinity, and the natural subdivision rule on the sphere gives rise to a sequence of tilings that is conformal in the sense above. Thus, Cannon's conjecture would be true if all such subdivision rules were conformal. ==References==