View source for Finite subdivision rule

{{Short description|Way to divide polygon into smaller parts}}
{{good article}}
[[Image:Hyperbolic orthogonal dodecahedral honeycomb.png|thumb|A perspective projection of a [[Hyperbolic small dodecahedral honeycomb|dodecahedral tessellation]] in '''[[Hyperbolic 3-manifold|H<sup>3</sup>]]'''. 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 [[closed manifold|closed]] [[3-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.<ref name="finite" /> Subdivision rules have been used in architecture, biology, and computer science, as well as in the study of [[hyperbolic manifold]]s. [[Substitution tiling]]s are a well-studied type of subdivision rule.

==Definition==
A subdivision rule takes a [[Tiling (mathematics)|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:
[[File:The binary subdivision rule.png|frameless|none|The binary subdivision rule]]

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 tiling|regular]], but doesn't have to be:

[[File:BinarySubdivisionComplex2.png|frameless|none|We start with a complex with four quadrilaterals and subdivide twice. All squares are type A tiles.]]

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 surface is a barycentric subdivision complex.<ref name="finite">J. W. Cannon, W. J. Floyd, W. R. Parry. ''[https://www.ams.org/ecgd/2001-05-08/S1088-4173-01-00055-8/S1088-4173-01-00055-8.pdf Finite subdivision rules]''. Conformal Geometry and Dynamics, vol. 5 (2001), pp. 153&ndash;196.</ref>

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

{| class="wikitable"
|-
! Name
! Initial tiles
! Generation 1
! Generation 2
! Generation 3
|-
| Half-kite
| [[File:penrose kile 0.svg|120px]]
| [[File:penrose kile 1.svg|120px]]
| [[File:penrose kile 2.svg|120px]]
| [[File:penrose kile 3.svg|120px]]
|-
| Half-dart
| [[File:penrose dart 0.svg|120px]]
| [[File:penrose dart 1.svg|120px]]
| [[File:penrose dart 2.svg|120px]]
| [[File:penrose dart 3.svg|120px]]
|-
| Sun
| [[File:penrose sun 0bis.svg|120px]]
| [[File:penrose sun 1.svg|120px]]
| [[File:penrose sun 2.svg|120px]]
| [[File:penrose sun 3.svg|120px]]
|-
| Star
| [[File:penrose star 0.svg|120px]]
| [[File:penrose star 1.svg|120px]]
| [[File:penrose star 2.svg|120px]]
| [[File:penrose star 3.svg|120px]]
|}

Certain [[rational mapping|rational maps]] give rise to finite subdivision rules.<ref name="rational">J. W. Cannon, W. J. Floyd, W. R. Parry. ''[https://www.ams.org/ecgd/2007-11-10/S1088-4173-07-00167-1/S1088-4173-07-00167-1.pdf Constructing subdivision rules from rational maps]''. Conformal Geometry and Dynamics, vol. 11 (2007), pp. 128&ndash;136.</ref> This includes most [[Lattès map]]s.<ref name="rationalB">J. W. Cannon, W. J. Floyd, W. R. Parry. ''Lattès maps and subdivision rules''. Conformal Geometry and Dynamics, vol. 14 (2010, pp. 113&ndash;140.</ref>

Every prime, non-split alternating [[knot complement|knot or link complement]] has a subdivision rule, with some tiles that do not subdivide, corresponding to the boundary of the link complement.<ref name="Alternating">B. Rushton. ''[https://www.ams.org/journals/ecgd/2010-14-01/S1088-4173-09-00205-7/S1088-4173-09-00205-7.pdf Constructing subdivision rules from alternating links]''. Conform. Geom. Dyn. 14 (2010), 1&ndash;13.</ref> 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]]:

[[File:Trefoil subdivision rule.png|none|300px|Trefoil subdivision rule]]
	 	
And this is the subdivision rule for the [[Borromean rings]], which is hyperbolic:
	 
[[File:Borromean subdivision rule.png|none|300px|Borromean subdivision rule]] 
	
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:
	
[[File:Finite subdivisions for the trefoil knot complement.png|300px|none|Subdivisions of the subdivision complex for the trefoil complement.]]
		
And for the Borromean rings:	 
	
[[File:Finite subdivisions for the Borromean rings complement.png|300px|none|Subdivisions of the subdivision complex for the Borromean rings complement.]]

==Subdivision rules in higher dimensions==

Subdivision rules can easily be generalized to other dimensions.<ref name="Torus">{{Cite journal | last1 = Rushton | first1 = B. | doi = 10.1007/s10711-012-9802-5 | title = A finite subdivision rule for the n-dimensional torus | journal = Geometriae Dedicata | volume = 167 | pages = 23–34 | year = 2012 | arxiv = 1110.3310 | s2cid = 119145306 }}</ref> For instance, [[barycentric subdivision]] is used in all dimensions. Also, binary subdivision can be generalized to other dimensions (where [[hypercube]]s get divided by every midplane), as in the proof of the [[Heine–Borel theorem]].

==Rigorous definition==
[[File:FourTorusSubdivision.svg|thumb|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''' <math> R </math> consists of the following.<ref name="finite" />

1. A finite 2-dimensional [[CW complex]] <math>S_R</math>, called the '''subdivision complex''', with a fixed cell structure such that <math>S_R</math> is the union of its closed 2-cells. We assume that for each closed 2-cell <math>\tilde{s}</math> of <math>S_R</math> there is a CW structure <math>s</math> on a closed 2-disk such that <math>s</math> has at least two vertices, the vertices and edges of <math>s</math> are contained in <math>\partial s</math>, and the characteristic map <math>\psi_s:s\rightarrow S_R</math> which maps onto <math>\tilde{s}</math> restricts to a homeomorphism onto each open cell.

2. A finite two dimensional CW complex <math>R(S_R)</math>, which is a subdivision of <math>S_R</math>.

3.A continuous cellular map <math>\phi_R:R(S_R)\rightarrow S_R</math> called the '''subdivision map''', whose restriction to every open cell is a homeomorphism onto an open cell.

Each CW complex <math>s</math> in the definition above (with its given characteristic map <math>\psi_s</math>) is called a '''tile type'''.

An <math>R</math>-complex for a subdivision rule <math>R</math> is a 2-dimensional CW complex <math>X</math> which is the union of its closed 2-cells, together with a continuous cellular map <math>f:X\rightarrow S_R</math> whose restriction to each open cell is a homeomorphism. We can subdivide <math>X</math> into a complex <math>R(X)</math> by requiring that the induced map <math>f:R(X)\rightarrow R(S_R)</math> restricts to a homeomorphism onto each open cell. <math>R(X)</math> is again an <math>R</math>-complex with map <math>\phi_R \circ f:R(X)\rightarrow S_R</math>. By repeating this process, we obtain a sequence of subdivided <math>R</math>-complexes <math>R^n(X)</math> with maps <math>\phi_R^n\circ f:R^n(X)\rightarrow S_R</math>.

Binary subdivision is one example:<ref name="biol"/>

[[File:The binary subdivision rule.png|frameless|none|The binary subdivision rule.]]

The subdivision complex can be created by gluing together the opposite edges of the square, making the subdivision complex <math>S_R</math> into a [[torus]]. The subdivision map <math>\phi</math> 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 <math>f:\mathbb{R}^2\rightarrow R(S_R)</math> 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==
[[File:CantorHistoryGraph.png|thumb|The history graph of the [[Cantor set|middle thirds]] subdivision rule.]]

Subdivision rules can be used to study the [[quasi-isometry]] properties of certain spaces.<ref name="RM"/> Given a subdivision rule <math>R</math> and subdivision complex <math>X</math>, we can construct a [[Graph (discrete mathematics)|graph]] called the '''history graph''' that records the action of the subdivision rule. The graph consists of the [[dual graph]]s of every stage <math>R^n(X)</math>, together with edges connecting each tile in <math>R^n(X)</math> with its subdivisions in <math>R^{n+1}(X)</math>.

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]].<ref name = "RM" />

==Applications==
{{multiple image
| direction = vertical
| header    = Applications of subdivision rules.
| width     = 220
| image1    = Darbeimam subdivision rule.svg
| alt1      = Girih tiles
| caption1  = An example of a subdivision rule used in the Islamic art known as [[girih]].

| image2    = Catmull-Clark subdivision of a cube.svg
| alt2      = Catmull-Clark subdivision
| caption2  = First three steps of [[Catmull–Clark subdivision surface|Catmull-Clark subdivision]] of a cube with subdivision surface below.

| image3    = Gray961.png
| alt3      = Bronchi
| caption3  = The branching nature of [[bronchi]] may be modelled by finite subdivision rules.
}}

Islamic [[Girih]] tiles in Islamic architecture are self-similar tilings that can be modeled with finite subdivision rules.<ref name="Girih"/> In 2007, [[Peter Lu|Peter J. Lu]] of [[Harvard University]] and Professor [[Paul Steinhardt|Paul J. Steinhardt]] of [[Princeton University]] published a paper in the journal ''[[Science (journal)|Science]]'' suggesting that girih tilings possessed properties consistent with [[self-similar]] [[fractal]] [[quasicrystalline]] tilings such as [[Penrose tiling]]s (presentation 1974, predecessor works starting in about 1964) predating them by five centuries.<ref name="Girih">{{cite journal | first1= Peter J. | last1=Lu | first2= Paul J. | last2= Steinhardt | year = 2007 | title = Decagonal and Quasi-crystalline Tilings in Medieval Islamic Architecture | journal = [[Science (journal)|Science]] | volume = 315 | pages = 1106–1110 | url = http://www.physics.harvard.edu/~plu/publications/Science_315_1106_2007.pdf | doi = 10.1126/science.1135491 | pmid = 17322056 | issue = 5815 | bibcode = 2007Sci...315.1106L | s2cid=10374218 | url-status = dead | archive-url = https://web.archive.org/web/20091007024019/http://www.physics.harvard.edu/~plu/publications/Science_315_1106_2007.pdf | archive-date = 2009-10-07 }}<br />{{cite web |title=Supporting Online Material |url=http://www.physics.harvard.edu/~plu/publications/Science_315_1106_2007_SOM.pdf |archive-url=https://web.archive.org/web/20090326095515/http://www.physics.harvard.edu/~plu/publications/Science_315_1106_2007_SOM.pdf |archive-date=2009-03-26 }}</ref>

[[Subdivision surface]]s 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 refines it to a mesh with more polygons by adding and shifting points according to different recursive formulas.<ref name="surface">D. Zorin. ''[http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.370.2714&rep=rep1&type=pdf Subdivisions on arbitrary meshes: algorithms and theory]''. Institute of Mathematical Sciences (Singapore) Lecture Notes Series. 2006.</ref> 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, you can identify a corresponding edge and vertex in the new one, plus several more edges and vertices).

Subdivision rules were applied by Cannon, Floyd and Parry (2000) to the study of large-scale growth patterns of biological organisms.<ref name="biol">J. W. Cannon, W. Floyd and W. Parry. [https://books.google.com/books?id=qZHyqUli9y8C&dq=%22james+w.+cannon%22+maths&pg=PA65 ''Crystal growth, biological cell growth and geometry''.] Pattern Formation in Biology, Vision and Dynamics, pp. 65&ndash;82. World Scientific, 2000. {{ISBN|981-02-3792-8}}, {{ISBN|978-981-02-3792-9}}.</ref> 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.<ref name="biol"/> Cannon, Floyd and Parry also applied their model to the analysis of the growth patterns of rat tissue.<ref name="biol"/> 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 [[fractal]]s.<ref name="biol"/> In particular they suggested that such "negatively curved" local structure is manifested in highly folded and highly connected nature of the brain and the lung tissue.<ref name="biol"/>

==Cannon's conjecture==

[[James W. Cannon|Cannon]], [[William Floyd (mathematician)|Floyd]], and [[Walter Parry|Parry]] first studied finite subdivision rules as an attempt to prove the following conjecture:

'''Cannon's conjecture''': Every [[Mikhail Leonidovich Gromov|Gromov]] [[hyperbolic group]] with a 2-sphere at infinity [[Geometric group action|acts geometrically]] on [[hyperbolic space|hyperbolic 3-space]].<ref name="RM">James W. Cannon. [https://doi.org/10.1007%2FBF02398434 ''The combinatorial Riemann mapping theorem''.] [[Acta Mathematica]] 173 (1994), no. 2, pp. 155&ndash;234.</ref>

Here, a geometric action is a cocompact, properly discontinuous action by isometries. This conjecture was partially solved by [[Grigori Perelman]] in his proof<ref name="perelman200211">{{cite arXiv|author=Perelman, Grisha |title=The entropy formula for the Ricci flow and its geometric applications |eprint = math.DG/0211159 | date = 11 November 2002}}</ref><ref name="perelman200303">{{cite arXiv|author=Perelman, Grisha|title=Ricci flow with surgery on three-manifolds |eprint=math.DG/0303109 | date = 10 March 2003}}</ref><ref name="perelman200307">{{cite arXiv|author=Perelman, Grisha|title=Finite extinction time for the solutions to the Ricci flow on certain three-manifolds |eprint=math.DG/0307245 |date = 17 July 2003}}</ref> 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 <ref name="CS">J. W. Cannon and E. L. Swenson, ''Recognizing constant curvature discrete groups in dimension 3''. [[Transactions of the American Mathematical Society]] 350 (1998), no. 2, pp. 809&ndash;849.</ref> 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.<ref name="RM" />

==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 [[Riemann surface|analytic structure]] on the surface. The Combinatorial Riemann Mapping Theorem gives necessary and sufficient conditions for this to occur.<ref name="RM"/>

Its statement needs some background. A tiling <math>T</math> of a ring <math>R</math> (i.e., a closed annulus) gives two invariants, <math>M_{\sup} (R,T)</math> and <math>m_{\inf} (R,T)</math>, called [[Extremal length#Discrete extremal length|approximate moduli]]. These are similar to the classical [[Extremal length#extremal distance in an annulus|modulus of a ring]]. They are defined by the use of '''weight functions'''. A weight function <math>\rho</math> assigns a non-negative number called a '''weight''' to each tile of <math>T</math>. Every path in <math>R</math> can be given a length, defined to be the sum of the weights of all tiles in the path. Define the '''height''' <math>H(\rho)</math> of <math>R</math> under <math>\rho</math> to be the infimum of the length of all possible paths connecting the inner boundary of <math>R</math> to the outer boundary. The '''circumference''' <math>C(\rho)</math> of <math>R</math> under <math>\rho</math> is the infimum of the length of all possible paths circling the ring (i.e. not nullhomotopic in R). The '''area'''<math>A(\rho)</math> of <math>R</math> under <math>\rho</math> is defined to be the sum of the squares of all weights in <math>R</math>. Then  define

: <math>M_{\sup} (R,T)=\sup \frac{H(\rho)^2}{A(\rho)},</math>

: <math>m_{\inf} (R,T)=\inf \frac{A(\rho)}{C(\rho)^2}.</math>

Note that they are invariant under scaling of the metric.

A sequence <math>T_1,T_2,\ldots</math> of tilings is '''conformal (<math>K</math>)''' if mesh approaches 0 and:

# For each ring <math>R</math>, the approximate moduli <math>M_{\sup}(R,T_i)</math> and <math>m_{\inf}(R,T_i)</math>, for all <math>i</math> sufficiently large, lie in a single interval of the form <math>[r,Kr]</math>; and
# Given a point <math>x</math> in the surface, a neighborhood <math>N</math> of <math>x</math>, and an integer <math>I</math>, there is a ring <math>R</math> in <math>N\smallsetminus\{x\}</math> separating ''x'' from the complement of <math>N</math>, such that for all large <math>i</math> the approximate moduli of <math>R</math> are all greater than <math>I</math>.<ref name="RM"/>

===Statement of theorem===

If a sequence <math>T_1,T_2,\ldots</math> of tilings of a surface is conformal (<math>K</math>) in the above sense, then there is a [[conformal structure]] on the surface and a constant <math>K'</math> depending only on <math>K</math> in which the classical moduli and approximate moduli (from <math>T_i</math> for <math>i</math> sufficiently large) of any given annulus are <math>K'</math>-comparable, meaning that they lie in a single interval <math>[r,K'r]</math>.<ref name="RM"/>

===Consequences===

The Combinatorial Riemann Mapping Theorem implies that a group <math>G</math> acts geometrically on <math>\mathbb{H}^3</math> 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.<ref name="CS"/>

==References==
{{reflist}}

== External links ==
* [https://web.archive.org/web/20130627120650/http://www.math.vt.edu/people/floyd/research/index.php 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.

{{Fractals}}
{{Areas of mathematics |collapsed}}

[[Category:Fractals]]
[[Category:Geometry]]