A perspective projection of a dodecahedral tessellation in H^{3}. Note the recursive structure: each pentagon contains smaller pentagons, which contain smaller pentagons. This is an example of a subdivision rule arising from a finite universe (i.e. a closed3-manifold).

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 regular geometric 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.^{[1]} Subdivision rules have been used in architecture, biology, and computer science, as well as in the study of hyperbolic manifolds. Substitution tilings are a well-studied type of subdivision rule.

A subdivision rule takes a tiling of the plane by polygons and turns it into a new tiling by subdividingeach 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:

polygon or other two-dimensional shape into smaller and smaller pieces. Subdivision rules in a sense are generalizations of regular geometric 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.^{[1]} Subdivision rules have been used in architecture, biology, and computer science, as well as in the study of hyperbolic manifolds. Substitution tilings are a well-studied type of subdivision rule.

tiling of the plane by polygons and turns it into a new tiling by subdividingeach 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:

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:

Here we start with a complex made of four quadrilaterals and subdivide it twice. All quadrilaterals are type A tiles.

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 surf

For instance, binary subdivision has one tile type and one edge type:

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:

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.^{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.[1]
}

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):

Name

Initial tiles

Generation 1

Generation 2

Generation 3

H

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.^{[2]} This includes most Lattès maps.^{[3]}

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.^{[4]} 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:

Subdivision rules in higher dimensions

Subdivision rules can easily be generalized to other dimensions.^{[5]} 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 in the proof of the Heine–Borel theorem.

Rigorous definition

A subdivision rule for the four-torus. The faces of the B tiles that subdivide can only touch C tiles, and the faces of the B tiles that don't only touch A tiles.

A finite subdivision rule$R$ consists of the following.^{[1]}

1. A finite 2-dimensional CW complex$S_{R}$, called the subdivision complex, with a fixed cell structure such that $$

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 subdi

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:

1. A finite 2-dimensional CW complex$S_{R}$, called the subdivision complex, with a fixed cell structure such that $}$

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 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}$. 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:^{[6]}

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.

Quasi-isometry properties

Subdivision rules can be used to study the quasi-isometry properties of certain spaces.^{[7]} Given a subdivision rule $R$ and subdivision complex $X$, we can construct a graph called the history graph that records the action of the subdivision rule. The graph consists of the dual graphs of every stage $R^{n}(X)$, together with edges connecting each tile in $R^{n}(X)$ with its subdivisions in $R^{n+1}(X)$.

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.^{[7]}