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.
Definition
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:
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 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):
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 finite subdivision rule consists of the following.[1]
1. A finite 2-dimensional CW complex, called the subdivision complex, with a fixed cell structure such that is the union of its closed 2-cells. We assume that for each closed 2-cell of there is a CW structure on a closed 2-disk such that has at least two vertices, the vertices and edges of are contained in , and the characteristic map which maps onto restricts to a homeomorphism onto each open cell.
2. A finite two dimensional CW complex , which is a subdivision of .
3.A continuous cellular map called the subdivision map, whose restriction to every open cell is a homeomorphism onto an open cell.
Each CW complex in the definition above (with its given characteristic map ) is called a tile type.
An -complex for a subdivision rule is a 2-dimensional CW complex which is the union of its closed 2-cells, together with a continuous cellular map whose restriction to each open cell is a homeomorphism. We can subdivide into a complex by requiring that the induced map restricts to a homeomorphism onto each open cell. is again an -complex with map . By repeating this process, we obtain a sequence of subdivided -complexes with maps .
The subdivision complex can be created by gluing together the opposite edges of the square, making the subdivision complex into a torus. The subdivision map 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 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 and subdivision complex , 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 , together with edges connecting each tile in with its subdivisions in .
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]
Applications
Applications of subdivision rules.
An example of a subdivision rule used in the Islamic art known as girih.
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 refines it to a mesh with more polygons by adding and shifting points according to different recursive formulas.[9] 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.[6] 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.[6] Cannon, Floyd and Parry also applied their model to the analysis of the growth patterns of rat tissue.[6] 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.[6] 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.[6]
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[10][11][12] 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 [13] 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.[7]
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.[7]
Its statement needs some background. A tiling of a ring (i.e., a closed annulus) gives two invariants, and , 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 assigns a non-negative number called a weight to each tile of . Every path in can be given a length, defined to be the sum of the weights of all tiles in the path. Define the height of under to be the infimum of the length of all possible paths connecting the inner boundary of to the outer boundary. The circumference of under is the infimum of the length of all possible paths circling the ring (i.e. not nullhomotopic in R). The area of under is defined to be the sum of the squares of all weights in . Then define
Note that they are invariant under scaling of the metric.
A sequence of tilings is conformal () if mesh approaches 0 and:
For each ring , the approximate moduli and , for all sufficiently large, lie in a single interval of the form ; and
Given a point in the surface, a neighborhood of , and an integer , there is a ring in separating x from the complement of , such that for all large the approximate moduli of are all greater than .[7]
Statement of theorem
If a sequence of tilings of a surface is conformal () in the above sense, then there is a conformal structure on the surface and a constant depending only on in which the classical moduli and approximate moduli (from for sufficiently large) of any given annulus are -comparable, meaning that they lie in a single interval .[7]
Consequences
The Combinatorial Riemann Mapping Theorem implies that a group acts geometrically on 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.[13]
References
^ abcJ. W. Cannon, W. J. Floyd, W. R. Parry. Finite subdivision rules. Conformal Geometry and Dynamics, vol. 5 (2001), pp. 153–196.
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.
Turkish politician Osman BaydemirMayor of DiyarbakırIn office2004–2014Preceded byFeridun ÇelikSucceeded byGültan KışanakMember of the Grand National Assembly of TurkeyIncumbentAssumed office 2014 Personal detailsBorn (1971-01-01) 1 January 1971 (age 53)Diyarbakır, Turkey Osman Baydemir (born 1971 in Diyarbakır) is a Kurdish politician, lawyer and human rights activist. He was the mayor of his home town of Diyarbakır from 2004 to 2014. He was a member of the Grand National Asse…
Iranian Iranologist and historian (born 1967) Touraj DaryaeeDaryaee in 2011Born1967 (age 56–57)Tehran, IranAcademic backgroundAlma materUniversity of California, Los AngelesThesisThe Fall of the Sāsānian Empire and the End of Late Antiquity: Continuity and Change in the Province of Persis (1999)Academic workDisciplineIranologyInstitutionsUniversity of California, IrvineÉcole pratique des hautes étudesCalifornia State University, FullertonMain interestsAncient/Medieval Iranian…
Pour le dessin animé, voir Le Jour de Christophe Colomb. Pour les articles homonymes, voir Christophe Colomb (homonymie). Jour de Christophe Colomb Peinture représentant la première arrivée de Christophe Colomb sur le continent américain (D. Puebla, 1862). Nom officiel Columbus Day Observé par les États-Unis, plusieurs pays d'Amérique latine, l'Espagne. Type Commémoration historique Signification Commémoration du premier voyage de Christophe Colomb en Amérique en 1492. Date 2e lu…
Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (mai 2018). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ? Comment …
Ini adalah nama Papua, (Biak), marganya adalah Dimara Johannes Abrahan DimaraLahir(1916-04-16)16 April 1916Korem, North Biak, Biak Numfor, Hindia BelandaMeninggal20 Oktober 2000(2000-10-20) (umur 84)Jakarta, IndonesiaDikebumikanKalibata, Jakarta SelatanPengabdian Kekaisaran Jepang (1942–1945) Indonesia (1945–1962) Dinas/cabang Kempei-Ho Tentara Nasional Indonesia Lama dinas1942–1945, 1945–1962Pangkat Pembantu Letnan Satu Mayor (1962) Kesatuan Batalyon Pattimura APRIS Dewan Pert…
SupremacyLagu oleh Musedari album The 2nd LawSisi-ASupremacy (Live dari BRITs)Dirilis20 Februari 2013 (2013-02-20)(see Waktu perilisan)Format Digital download CD-R DirekamOktober 2011 – Juli 2012 diCapitol Studios(Los Angeles, Amerika Serikat)20 Februari 2013 diThe O2 Arena(London, Inggris)Genre Progressive rock[1] hard rock[1] symphonic rock Durasi4:55 (Versi album)3:40 (Radio edit)Label Warner Bros. Helium-3 PenciptaMatthew BellamyProduserMuse Video musikSupremacy di You…
Koneksi normal antara pengguna (Alice) dan server. Jabat tangan tiga arah dilakukan dengan benar. SYN Flood. Penyerang (Mallory) mengirimkan beberapa paket tetapi tidak mengirim ACK kembali ke server. Karena itu, koneksi setengah terbuka dan menghabiskan sumber daya server. Alice, pengguna yang sah, mencoba untuk terhubung tetapi server menolak untuk membuka koneksi yang mengakibatkan penolakan layanan. Sebuah SYN flood adalah bentuk serangan penolakan layanan di mana penyerang dengan cepat memu…
Disambiguazione – Se stai cercando altri significati, vedi Joystick (disambigua). Questa voce o sezione sugli argomenti periferiche e videogiochi non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento. Il joystick standard dell'Atari 2600, esempio della configurazione minima di un joystick per computer/videogiochi …
Species of bird Brown jay Adult bird.Aserrí, Costa Rica Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Domain: Eukaryota Kingdom: Animalia Phylum: Chordata Class: Aves Order: Passeriformes Family: Corvidae Genus: PsilorhinusRüppell, 1837 Species: P. morio Binomial name Psilorhinus morio(Wagler, 1829) Range (click to magnify) Synonyms Cyanocorax morio The brown jay (Psilorhinus morio) is a large jay native to North and Central America. Description S…
Військово-музичне управління Збройних сил України Тип військове формуванняЗасновано 1992Країна Україна Емблема управління Військово-музичне управління Збройних сил України — структурний підрозділ Генерального штабу Збройних сил України призначений для плануван…
جائحة فيروس كورونا في سوريا 2020 المرض مرض فيروس كورونا 2019 السلالة SARS-CoV-2 أول حالة 22 مارس 2020 المنشأ ووهان، خوبي، الصين المكان سوريا الوفيات 3163 الحالات المؤكدة 57216 حالات متعافية 53971 الحالات النشطة 82 الموقع الرسمي حالات الإصابة المسجلة بمرض كوفيد-19 في الجمهورية العربية السوري…
Election for the governorship of the U.S. state of Nebraska 1974 Nebraska gubernatorial election ← 1970 November 5, 1974 1978 → Nominee James Exon Richard D. Marvel Ernie Chambers (Write-in) Party Democratic Republican Independent Running mate Gerald T. Whelan Anne S. Batchelder Popular vote 267,012 159,780 24,320 Percentage 59.2% 35.4% 5.4% County resultsExon: 40–50% 50–60% &…
English investigative reporter (1943–2022) Andrew JenningsBorn(1943-09-03)3 September 1943Kirkcaldy, ScotlandDied8 January 2022(2022-01-08) (aged 78)Carlisle, EnglandNationalityBritish[1]Alma materUniversity of HullOccupation(s)Journalist, author Andrew Jennings (3 September 1943 – 8 January 2022) was a British investigative reporter. He was best known for his work investigating and writing about corruption in the IOC and FIFA. Early life Jennings was born in Kirkcaldy, Sco…
Species of flowering plant in the lychee family Sapindaceae Not to be confused with Acer platanoides, Platanus occidentalis (found in North America), or Ficus sycomorus (found in Africa and the Middle East). Acer pseudoplatanus Acer pseudoplatanus in the Bergpark Wilhelmshöhe, Kassel, Germany Conservation status Least Concern (IUCN 3.1)[1] Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Clade: Rosids Order: Sapindales Family: Sapi…
У этого термина существуют и другие значения, см. Доллар (значения). Доллар США[a] англ. US Dollar фр. Dollar des États-Unis[b] Коды и символы Коды ISO 4217 USD (840) Символы $ • US$ Территория обращения Страна-эмитент США Бермуды Бонайре Виргинские Острова (Великобрит…
World Wrestling Entertainment pay-per-view event Night of ChampionsPromotional poster featuring Kane holding the World Heavyweight ChampionshipPromotionWorld Wrestling EntertainmentBrand(s)RawSmackDownDateSeptember 19, 2010CityRosemont, IllinoisVenueAllstate ArenaAttendance13,851[1]Buy rate165,000Pay-per-view chronology ← PreviousSummerSlam Next →Hell in a Cell Night of Champions chronology ← Previous2009 Next →2011 The 2010 Night of Champions was the fourth a…
Soviet gymnast; American instructor since 1991 Olga KorbutOlga Korbut c. 1972Personal informationFull nameOlga Valentinovna KorbutNickname(s)Sparrow from Minsk[1]Country represented Soviet UnionBorn (1955-05-16) 16 May 1955 (age 69)Hrodna, Belarusian SSR, Soviet Union (USSR)HometownScottsdale, Arizona since 2002Height4 ft 11 in (150 cm)[citation needed]Weight84 lb; 38 kg (6 st)[citation needed]DisciplineWomen's artistic…
ReservationUte Mountain ReservationReservation FlagSealLocation of the Ute Mountain ReservationConstitution1940Seat of GovernmentTowaoc, ColoradoGovernment • BodyTribal Administration Department • Chairman of the Tribal Administration DepartmentHarold CuthairArea • Total2,238 km2 (864 sq mi)Population (2020) • Total1,656Time zoneMST/MDTWebsite[1] The Ute Mountain Ute Tribe /ˈjuːt/ (Ute dialect: Wʉgama Núuchi) is one of three…
American music critic Downes (c. 1950); the caption reads: To the Sibelius Museum, in all homage to the greatest living master. Edwin Olin Downes, better known as Olin Downes (January 27, 1886 – August 22, 1955), was an American music critic, known as Sibelius's Apostle for his championship of the music of Jean Sibelius. As critic of The New York Times, he exercised considerable influence on musical opinion, although many of his judgments have not stood the test of time. Life and wor…