Finite subdivision rule

A simple subdivision rule with three tile types. All C tiles are squares because they have four vertices, but look like triangles in the subdivisions of the A and B tiles. This is an example of how subdivision rules allow variety in the way each tile is drawn.

An example of using a subdivision rule. Here, we're using the subdivision rule above on one of its A tiles to get more and more refined coverings of the triangle.

In mathematics, a finite subdivision rule is a recursive way of dividing a polygon or other two-dimensional shape into smaller and smaller pieces. Subdivision rules in a sense are generalizations of fractals. Instead of repeating exactly the same design over and over, they have slight variations in each stage, allowing a richer structure while maintaining the elegant style of fractals.

Cannon's conjecture

Cannon, Floyd, and Parry first studied finite subdivision rules in an attempt to prove the following

Cannon's conjecture: Every Gromov hyperbolic group with a 2-sphere at infinity acts geometrically on hyperbolic 3-space.

A perspective projection of a dodecahedral tessellation in H³. Note the recursive structure: each pentagon contains smaller pentagons, which contain smaller pentagons. This is an example of a subdivision rule arising from a hyperbolic group.

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) than any Gromov hyperbolic group that is a 3-manifold group must act geometrically on hyperbolic 3-space. However, it still remains to show 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.

Rigorous definition

A finite subdivision rule $R$ consists of the following.

1. 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.

2. A finite two dimensional CW complex $R(S_R)$, which is a subdivision of $S_R$.

3.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.

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$. By repeating this process, we obtain a sequence of subdivided $R$-complexes $R^n(X)$ with maps $\phi_R^n\circ f:R^n(X)\rightarrow S_R$.

Binary subdivision is one example:

The subdivision complex can be created by gluing together the opposite edges of the square, making the subdivision complex $S_R$ into a torus. The subdivision map $\phi$ is the doubling map on the torus, wrapping the meridian around itself twice and the longitude around itself twice. This is a four-fold covering map. The plane, tiled by squares, is a subdivision complex for this subdivision rule, with the structure map $f:\mathbb{R}^2\rightarrow R(S_R)$ given by the standard covering map. Under subdivision, each square in the plane gets subdivided into squares of one-fourth the size.

Combinatorial Riemann Mapping Theorem

Subdivision rules give a sequence of tilings of a surface, and tilings give an idea of distance, length, and area (by letting each tile have length and area 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$. Then define

$M_{sup} (R,T)=\sup \frac{H(\rho)^2}{A(\rho)}$ 

$m_{inf} (R,T)=\inf \frac{A(\rho)}{C(\rho)^2}$. 

Note that they are invariant under scaling of the metric.

A sequence $T_1,T_2,...$ of tilings is conformal ($K$) if mesh approaches 0 and:

1. 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
2. Given a point $x$ in the surface, a neighborhood $N$ of $x$, and an integer $I$, there is a ring $R$ in $N\setminus\{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,...$ 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.

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.

A triangle subdivided repeatedly using barycentric subdivision. The pictures are distorted by circle packing. The complement of the large circles is becoming a Sierpinski carpet

Certain rational maps give rise to finite subdivision rules. This includes most Lattès maps.

Every prime, non-split alternating knot or link complement an associated canonical finite subdivision rules, with tiles that do not subdivide, corresponding to the boundary of the link complement. Two interesting examples are the trefoil knot complement's subdivision rule:

Trefoil subdivision rule

And the Borromean rings complements' subdivision rule:

Borromean subdivision rule

In each case, we can the first tile type to be our subdivision complex $X$. Then we get cell structures that are more and more refined, for the trefoil complement:

Subdivisions of the subdivision complex for the trefoil complement.

And for the Borromean rings complement:

Subdivisions of the subdivision complex for the Borromean rings complement.

There are also finite subdivision rules for all closed hyperbolic 3-manifolds created by gluing together right-angled hyperbolic polyhedra.

Applications to biology

Main article: James W. Cannon

The ideas of combinatorial conformal geometry that underlie Cannon's proof of the "combinatorial Riemann mapping theorem", were applied by Cannon, Floyd and Parry (2000) to the study of large-scale growth patterns of biological organisms. Cannon, Floyd and Parry produced a mathematical growth model which demonstrated that some systems determined by simple finite subdivision rules can results 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. Cannon, Floyd and Parry 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 (see section 3.4 of ) that such "negatively curved" local structure is manifested in highly folded and highly connected nature of the brain and the lung tissue.

Applications in other areas

Girih tiles in Islamic architecture are also related to finite subdivision rules, as are subdivision surfaces in computer graphics .

An example of a subdivision rule used in the Islamic art known as girih.

External links

• Bill Floyd's research page. This page contains most of the research papers by Cannon, Floyd and Parry on subdivision rules, as well as a gallery of subdivision rules.

• Brian Rushton's research page. This page contains a gallery of subdivision rules of 3-manifolds and n-cubes.