В математике конечное правило подразделения — это рекурсивный способ деления многоугольника и других двумерных фигур на всё меньшие и меньшие части. Правила подразделения в этом смысле является обобщением фракталов . Вместо повторения одного и того же узора снова и снова здесь имеются небольшие изменения на каждом шаге, что позволяет получить более богатые структуры, сохраняя при этом поддержку элегантного стиля фракталов . Правила подразделения используются в архитектуре, биологии и информатике, а также при изучении . Подстановки плиток являются хорошо изученным видом правил подразделения.

Определение

Правило подразделения берёт замощение на плоскости многоугольниками и превращает его в новое замощение путём деления каждого многоугольника на меньшие многоугольники. Правило конечно , если имеется лишь конечное число путей деления каждого многоугольника. Каждый способ деления плитки называется типом плитки . Каждый тип плитки представляется меткой (обычно — буквой). Каждый тип плитки делится на меньшие типы плиток. Каждое ребро также делится на конечное число типов рёбер . Конечные правила подразделения могут только делить плитки, которые состоят из многоугольников, помеченных типами плиток. Такие замощения называются комплексами подразделения для правила подразделения. Если задан какой-либо комплекс подразделения для правила подразделения, мы можем делить его снова и снова для получения последовательности замощений.

Например, бинарное подразделение имеет один тип плитки и один тип ребра:

Поскольку плитки являются только четырёхугольниками, бинарное подразделение может дать замощение, состоящее только из четырёхугольников. Это означает, что комплексы подразделения являются мозаиками из четырёхугольников. Мозаика может быть правильной , но не обязана быть:

Здесь мы начинаем с четырёх четырёхугольников и подразделяем их дважды. Все квадраты являются плитками типа A.

Примеры конечных правил подразделения

Барицентрическое подразделение является примером правила подразделения с одним типом рёбер (которые подразделяются на два ребра) и одним типом плитки (треугольник, который подразделяется на 6 меньших треугольников). Любая триангулированная поверхность является комплексом барицентрического подразделения .

Мозаика Пенроуза может быть получена с помощью правила подразделения на наборе из четырёх типов плиток (кривые в таблице ниже только помогают показать, как плитки складываются вместе):

Название	Начальные плитки	Поколение 1	Поколение 2	Поколение 3
Полудельтоид
Полустрела
Солнце
Звезда

Некоторые рациональные отображения дают начало конечным правилам подразделения . Они включают большинство .

Любое простое неразделимое альтернирующее дополнение узла или зацепления имеет правило подразделения с некоторыми плитками, которые не подразделяются согласно границам дополнения зацепления . Правила подразделения показывают, как бы выглядело ночное небо, если бы кто-то жил в дополнении узла В этом случае вселенная заворачивается в себя (т.е. не односвязна ), и наблюдатель видел бы видимую часть вселенной повторяющейся в бесконечной мозаике. Правило подразделения описывает эту мозаику.

Правило подразделения выглядит по-разному для различных геометрий. Вот правило подразделения для трилистника , который не является гиперболическим зацеплением :

А вот правило подразделения для колец Борромео , которые гиперболичны:

В каждом случае правило подразделения действует на некоторое замощение сферы (т.е. ночного неба), но проще нарисовать малую часть звёздного неба, соответствующего отдельной плитке, многократно подразделяемой. Вот что происходит для трилистника:

И для колец Борромео:

Правила подразделения в других размерностях

Правила подразделения можно обобщить на другие размерности . Например, барицентрическое подразделение применимо во всех размерностях. Бинарное подразделение также может быть обобщено на другие размерности (где гиперкубы делятся серединными гиперплоскостями), как в доказательстве леммы Гейне — Бореля .

Строгое определение

Конечное правило подразделения ${\displaystyle R}$ состоит из следующего .

1. Конечный 2-мерный CW-комплекс ${\displaystyle S_{R}}$ , называемый комплексом подразделения , с фиксированной структурой ячеек, такой что ${\displaystyle S_{R}}$ является объединением замкнутых 2-ячеек. Мы предполагаем, что для каждой замкнутой 2-ячейки ${\displaystyle {\tilde {s}}}$ комплекса ${\displaystyle S_{R}}$ существует CW структура ${\displaystyle s}$ на замкнутых 2-дисках, такая, что ${\displaystyle s}$ имеет по меньшей мере две вершины, вершины и рёбра ${\displaystyle s}$ содержатся в ${\displaystyle \partial s}$ , и характеристическое отображение ${\displaystyle \psi _{s}:s\rightarrow S_{R}}$ , отображающее в ${\displaystyle {\tilde {s}}}$ , ограничивается гомеоморфизмом в каждую открытую ячейку.

2. Конечный двухмерный CW-комплекс ${\displaystyle R(S_{R})}$ , который является подразделением ${\displaystyle S_{R}}$ .

3. Непрерывное отображение ячеек ${\displaystyle \phi _{R}:R(S_{R})\rightarrow S_{R}}$ , называемое отображением подразделения , ограничение которого на каждую открытую ячейку является гомеоморфизмом.

Каждый CW-комплекс ${\displaystyle s}$ в вышеприведённом определении (с характеристическим отображением ${\displaystyle \psi _{s}}$ ) называется типом плитки .

${\displaystyle R}$ -комплекс для правила подразделения ${\displaystyle R}$ является двумерным CW-комплексом ${\displaystyle X}$ , который является объединением замкнутых 2-ячеек, вместе с непрерывным отображением ячеек ${\displaystyle f:X\rightarrow S_{R}}$ , ограничение которого на каждую открытую ячейку является гомеоморфизмом. Мы можем подразделить ${\displaystyle X}$ в комплекс ${\displaystyle R(X)}$ , потребовав, чтобы порождённое отображение ${\displaystyle f:R(X)\rightarrow R(S_{R})}$ ограничивалось гомеоморфизмом в каждую ограниченную ячейку. ${\displaystyle R(X)}$ снова ${\displaystyle R}$ -комплекс с отображением ${\displaystyle \phi _{R}\circ f:R(X)\rightarrow S_{R}}$ . Повторяя процесс, мы получим последовательность подразделённых ${\displaystyle R}$ -комплексов ${\displaystyle R^{n}(X)}$ с отображениями ${\displaystyle \phi _{R}^{n}\circ f:R^{n}(X)\rightarrow S_{R}}$ .

Бинарное подразделение является одним из примеров:

Комплекс подразделения может быть создан склеиваем вместе противоположных рёбер квадрата, что превращает комплекс подразделения ${\displaystyle S_{R}}$ в тор . Отображение подразделения ${\displaystyle \phi }$ является удвоенным отображением тора, оборачивающим меридиан относительно себя дважды, и то же самое для широты. То есть это четырёхкратное накрытие . Плоскость, замощённая квадратами, является комплексом подразделения для этого правила подразделения со структурным отображением ${\displaystyle f:\mathbb {R} ^{2}\rightarrow R(S_{R})}$ , заданным стандартным отображением накрытия. При подразделении каждый квадрат на плоскости подразделяется на квадраты в четверть размера.

Свойства квазиизометрии

Правила подразделения могут быть использованы для изучения свойств квазиизометрии некоторых поверхностей . Если задано правило подразделения ${\displaystyle R}$ и комплекс подразделения ${\displaystyle X}$ , мы можем построить граф , называемый графом истории , в который заносятся действия правила подразделения. Граф состоит из двойственных графов каждого шага ${\displaystyle R^{n}(X)}$ , вместе с рёбрами, соединяющими каждую плитку из ${\displaystyle R^{n}(X)}$ с её подразделениями в ${\displaystyle R^{n+1}(X)}$ .

Свойства квазиизометрии графов истории можно изучать с помощью правил подразделения. Например, граф истории является квазиизометрией гиперболического пространства в точности тогда, когда правила подразделения являются конформными , как описано в .

Приложения

Мозаика Гирих в исламской архитектуре — самоподобное замощение, которое можно смоделировать конечными правилами подразделения . В 2007 из Гарвардского университета и профессор из Принстонского университета опубликовали статью в журнале Science с гипотезой, что эти мозаики обладают свойствами, согласующимися с самоподобными фрактальными квазикристальными замощениями, такими как мозаики Пенроуза (мозаика предложена в 1974), но мозаики гирих использовались пять столетий ранее .

в компьютерной графике использует правила подразделения для детализации поверхности до любого заданного уровня точности. На этих подразделениях поверхности (таких как ) берётся полигональная сетка (используемая для 3D-анимации в фильмах) и детализируется к сетке с большим числом многоугольников путём добавления и сдвига точек согласно различным рекурсивным формулам . Хотя много точек в этом процессе сдвигаются, каждая новая сетка комбинаторно является подразделением старой сетки (что означает, что для любого ребра и вершины старой сетки можно указать ребро и вершину новой сетки, плюс несколько добавочных рёбер и вершин).

Правила подразделения использовали Кэннон, Флойд и Парри (2000) для изучения структур растущих биологических организмов . Кэннон, Флойд и Парри разработали математическую модель роста, которая демонстрирует, что некоторые системы, определённые простыми конечными правилами подразделения, дают в результате объекты (в их случае, — ствол дерева), формы большого объёма у которых со временем колеблются широко, хотя локальные правила подразделения остаются теми же самыми . Кэннон, Флойд и Парри применили также свою модель к анализу роста тканей крыс . Они высказали предположение, что "отрицательно выгнутая" (или неевклидова) природа микроскопических структур роста биологических организмов является одой из ключевых причин, почему организмы в крупном масштабе не выглядят как кристаллы или многогранники, а, фактически, во многих случаях имеют сходство с самоподобными фракталами . В частности, они высказали предположение, что такая "отрицательно выгнутая" локальная структура проявляется в крайне складчатой и крайне связанной природе тканей мозга и лёгких .

Гипотеза Кэннона

, и Парри первыми начали изучать конечные правила подразделения в попытке доказать следующую гипотезу:

Гипотеза Кэннона : Любая громовская гиперболическая группа с 2-сферой на бесконечности на гиперболическое 3-пространство .

Здесь геометрическое действие — это компактное, вполне разрывное действие изометрий. Гипотеза была частично решена Григорием Перельманом в его доказательстве гипотезы Тёрстона , которая утверждает (в частности), что любая громовская гиперболическая группа, являющаяся группой 3-многообразия, должна действовать геометрически в гиперболическом 3-пространстве. Однако остаётся показать, что громовская гиперболическая группа с 2-сферой на бесконечности является группой 3-многообразия.

Кэннон и Свенсон показали , что гиперболическая группа с 2-сферой на бесконечности имеет связанное с ней правило подразделения. Если это правило подразделения в определённом смысле конформно, группа будет группой 3-многообразия с геометрией гиперболического 3-пространства .

Комбинаторная теорема Римана об отображениях

Правила подразделения даёт последовательность замощений поверхности, а замощения дают идею расстояния, длины и площади (если считать, что каждая плитка имеет длину и площадь 1). В пределе расстояние, которое получается из этих замощений, может в некотором смысле сходиться к аналитической структуре на поверхности. Комбинаторная теорема Римана об отображениях даёт необходимое и достаточное условие, чтобы это произошло .

Для формулировки теоремы требуется некоторая подготовка. Замощение ${\displaystyle T}$ кольца ${\displaystyle R}$ даёт два инварианта, ${\displaystyle M_{sup}(R,T)}$ и ${\displaystyle m_{inf}(R,T)}$ , называемых . Они подобны классическому модулю кольца . Они определяются с помощью функций веса . Функция веса ${\displaystyle \rho }$ каждой плитке замощения ${\displaystyle T}$ сопоставляет неотрицательное число, называемое весом . Для любого пути в ${\displaystyle R}$ можно задать длину как сумму весов всех плиток в пути. Определим высоту ${\displaystyle H(\rho )}$ пути в ${\displaystyle R}$ по ${\displaystyle \rho }$ как инфимум длины всех возможных путей, соединяющих внутреннюю границу ${\displaystyle R}$ со внешней границей. Длина окружности ${\displaystyle C(\rho )}$ круга ${\displaystyle R}$ по ${\displaystyle \rho }$ — это инфимум длины всех возможных путей, образующих цикл в кольце (т.е. не гомотопных нулю в R). Площадь ${\displaystyle A(\rho )}$ кольца ${\displaystyle R}$ по ${\displaystyle \rho }$ определяется как сумма квадратов всех весов в ${\displaystyle R}$ . Теперь определим

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

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

Заметим, что эти величины инвариантны при масштабировании метрики.

Последовательность ${\displaystyle T_{1},T_{2},...}$ плиток является конформным ( ${\displaystyle K}$ ) , если величина ячеек стремится к 0 и:

1. Для всех колец ${\displaystyle R}$ аппроксимирующие модули ${\displaystyle M_{sup}(R,T_{i})}$ и ${\displaystyle m_{inf}(R,T_{i})}$ для всех достаточно больших ${\displaystyle i}$ лежат в одном интервале вида ${\displaystyle [r,Kr]}$
2. Если задана точка ${\displaystyle x}$ на поверхности, окрестность ${\displaystyle N}$ точки ${\displaystyle x}$ и целое число ${\displaystyle I}$ , то существует кольцо ${\displaystyle R}$ в ${\displaystyle N\setminus \{x\}}$ , отделяющее x от дополнения ${\displaystyle N}$ , так что с некоторого ${\displaystyle i}$ аппроксимирующие модули кольца ${\displaystyle R}$ больше числа ${\displaystyle I}$ .

Утверждение теоремы

Если последовательность ${\displaystyle T_{1},T_{2},...}$ плиток на поверхности является конформной ( ${\displaystyle K}$ ) в вышеописанном смысле, то существует на поверхности и константа ${\displaystyle K'}$ , зависящая только от ${\displaystyle K}$ , для которых классические модули и аппроксимирующие модули (для ${\displaystyle T_{i}}$ при достаточно большом ${\displaystyle i}$ ) любого заданного кольца ${\displaystyle K'}$ -сопоставимы, что означает, что они лежат в одном интервале ${\displaystyle [r,K'r]}$ .

Следствия

Из комбинаторной теоремы Римана об отображениях вытекает, что группа ${\displaystyle G}$ действует геометрически на ${\displaystyle \mathbb {H} ^{3}}$ тогда и только тогда, когда группа является громовской гиперболической, имеет сферу на бесконечности и естественные правила подразделения на сфере дают последовательность мозаик, которые конформны в описанном выше смысле. Таким образом, гипотеза Кэннона будет верна, если все такие правила подразделения конформны .

Примечания

Литература

• B. Rushton. A finite subdivision rule for the n-dimensional torus // Geometriae Dedicata. — 2012. — Т. 167 . — С. 23–34 . — doi : .
• Peter J Lu. Decagonal and quasi-crystalline tilings in medieval islamic architecture // Science. — 2007. — Т. 315 . — С. 1106–1110 . — doi : . — Bibcode : . — .
• Peter J. Lu, Paul J. Steinhardt. Decagonal and Quasi-crystalline Tilings in Medieval Islamic Architecture // Science . — 2007. — Т. 315 , вып. 5815 . — С. 1106–1110 . — doi : . — Bibcode : . — .
• J. W. Cannon, W. J. Floyd, W. R. Parry. Finite subdivision rules // Conformal Geometry and Dynamics. — 2001. — Т. 5 .
• J. W. Cannon, W. J. Floyd, W. R. Parry. Constructing subdivision rules from rational maps // Conformal Geometry and Dynamics. — 2007. — Т. 11 .
• J. W. Cannon, W. J. Floyd, W. R. Parry. Lattès maps and subdivision rules // Conformal Geometry and Dynamics. — 2010. — Т. 14 .
• J. W. Cannon, W. J. Floyd, W. R. Parry. Pattern Formation in Biology, Vision and Dynamics. — World Scientific, 2000. — ISBN 981-02-3792-8 , 978-981-02-3792-9..
• B. Rushton. Constructing subdivision rules from alternating links // Conform. Geom.. — 2010. — Вып. 14 .
• James W. Cannon. The combinatorial Riemann mapping theorem // Acta Mathematica . — 1994. — Т. 173 , вып. 2 .
• J. W. Cannon, E. L. Swenson. Recognizing constant curvature discrete groups in dimension 3 // Transactions of the American Mathematical Society. — 1998. — Т. 350 , вып. 2 .
• D. Zorin. Subdivisions on arbitrary meshes: algorithms and theory. — Institute of Mathematical Sciences (Singapore), 2006. — (Lecture Notes Series).

Ссылки

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