Finite subdivision rule

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

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.

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

...
Wikipedia