Круги лепестковые: Круги лепестковые радиальные Klingspor для станков купить в Абразивкомплект

Лепестки, цветы и круглые упаковки

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

Дэвид Остин
Государственный университет Гранд-Вэлли
Электронная почта Дэвида Остина

Введение

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

Чтобы ввести упаковки кругов, мы начнем с двумерной ориентированной поверхности $S$. В примере слева внизу поверхность топологически эквивалентна замкнутому диску. Затем мы рассматриваем триангуляцию $T$ поверхности, разложение поверхностей на треугольники, которые подходят друг к другу край к краю.

Вот упаковка кругов, связанная с этой триангуляцией:

Вообще говоря, упаковка кругов связана с триангуляцией $T$, когда

	1. Окружность связана с каждой вершиной триангуляции.
	2. Ребро подразумевает касание между двумя окружностями, связанными с его конечными точками.
	3. Грань подразумевает тройку касаний.

Чтобы увидеть, что приведенная выше упаковка окружностей связана с триангуляцией $T$, мы нарисуем нерв упаковки, добавив вершину в центре каждой окружности и ребра для касательных окружностей.

Если мы добавим к нерву треугольные грани, то найдем носитель упаковки круга, который является триангуляцией $T’$ новой поверхности $S’$. Заметим, что $S’$ топологически эквивалентна (гомеоморфна) исходной поверхности $S$, а $T’$ комбинаторно эквивалентна исходной триангуляции $T$. Таким образом, носитель обеспечивает геометрическую реализацию триангуляции $T$.

В более общем плане нет причин ограничиваться упаковками окружностей в евклидовой плоскости ${\Bbb C}$; мы также можем искать упаковки в гиперболической плоскости ${\Bbb D}$ и сфере Римана ${\Bbb P}$. Вот, например, упаковка того же комплекса в гиперболической плоскости.

Кроме того, мы можем начать с триангуляции любой двумерной ориентированной поверхности с границей или без нее; однако для простоты мы будем рассматривать здесь только односвязные поверхности. (Помните, что поверхность называется односвязной, если любую петлю на поверхности можно непрерывно стянуть в точку.)

Обратите внимание, что эта экспозиция предназначена для того, чтобы передать общую картину, поэтому мы намеренно сделаем несколько сокращений и пропустим некоторые детали и технические детали, которые можно найти в ссылках. Имея это в виду, давайте научимся создавать упаковки кругов.

Как изготовить круглые насадки

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

Метод релаксации: Предположим, мы хотим найти линейную функцию $f(x)$ на интервале $[a,b]$ с заданными значениями в точках $a$ и $b$.

Конечно, мы знаем, что существует единственная линейная функция, удовлетворяющая этому условию. Метод, известный как релаксация , предоставляет алгоритм для его нахождения.

Обратите внимание, что линейные функции характеризуются локальным условием; а именно, значение функции в точке $c$ есть среднее значение $f$ в двух точках, равноотстоящих от $c$. То есть

$$f(c)=\frac{f(c-h)+f(c+h)}{2}.$$

Чтобы начать наш алгоритм, мы строим равноотстоящую сетку точек $x_0, x_1, \ldots, x_n$, где $x_0 = a$ и $x_n = b$, и случайным образом присваиваем значения внутренним точкам.
Начиная с самой левой точки $x_1$, мы заменяем значение в $x_1$ средним значением соседних точек.
Затем мы делаем то же самое для $x_2$.
Перебирая все внутренние точки, получаем новые значения:
Повторение снова дает:

После 10 и 25 итераций имеем

Обратите внимание, что каждый шаг алгоритма нарушает локальное условие, которое мы установили на предыдущем шаге. Тем не менее значения во внутренних точках сходятся к значениям искомой линейной функции.

В более общем смысле этот метод релаксации применяется в более высоких измерениях к проблеме нахождения гармонических функций с заданными граничными значениями.

Используя ту же идею, мы найдем упаковку кругов для треугольной двумерной ориентированной поверхности с краем. Рассмотрим показанную здесь триангуляцию замкнутого диска

и предположим, что мы задаем радиусы окружностей, связанных с граничными вершинами.

Нахождение радиусов: Определим радиусы окружностей, связанных с внутренними вершинами, для создания упаковки окружностей

Действуя так же, как в нашем алгоритме нахождения линейной функции, применим этот шаг к каждой из внутренних вершин по очереди. Конечно, обновление радиуса одной окружности может нарушить сумму углов, которую мы ранее скорректировали. Следовательно, после одного прохода по всем внутренним точкам у нас, скорее всего, не будет упаковки кругов; однако можно доказать, что общая ошибка сумм углов уменьшилась. Поэтому мы продолжаем проходить через внутренние вершины, обновляя их радиусы, пока все суммы углов не окажутся в пределах желаемого допуска $2\pi$.

Нахождение центров: Теперь, когда у нас есть радиусы внутренних кругов, нам еще нужно определить центры кругов. Выберем окружность $C_0$ радиуса $r_0$ и один из ее лепестков $C_1$ радиуса $r_1$. Как только мы выбираем центр для $C_0$, центр $C_1$ должен находиться на расстоянии $r_0+r_1$.

Затем мы раскладываем лепестки $C_0$ по одному, начиная с $C_2$, которая касается $C_0$ и $C_1$.

Продолжая таким же образом, мы размещаем все лепестки $C_0$.

Мы продолжаем этот процесс, размещая лепестки $C_1$ и так далее, пока не будут выложены все круги.

Оказывается, найденная нами упаковка кругов единственна с точностью до изометрии. Это станет ясно, если мы заметим, что радиусы внутренних окружностей определяются однозначно, а все центры определяются, когда мы выбираем центры $C_0$ и $C_1$.

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

В нашем обсуждении мы построили упаковку кругов, потребовав $\theta_v = 2\pi$ в каждой из внутренних вершин. Интересные примеры и явления можно найти, потребовав, чтобы $\theta_v = 2\pi n$ для некоторого $n>1$ в некоторых внутренних вершинах. Две приведенные ниже упаковки имеют одинаковые граничные радиусы; однако мы требуем, чтобы вершина, связанная с заштрихованным кругом, удовлетворяла $\theta_v=2\pi$ слева и $\theta_v=4\pi$ справа. Это приводит к тому, что лепесток цветка обвивается вокруг центрального круга более одного раза, что приводит к явлению ветвления, которое мы здесь исследовать не будем.

В более общем смысле мы также можем создавать упаковки кругов в гиперболической плоскости, где граничные круги имеют бесконечный радиус; мы называем это максимальной упаковкой триангуляции $T$ и обозначаем ее ${\cal P}_T$. Например, вот такая упаковка триангуляции, с которой мы только что работали. Это в некотором смысле каноническая упаковка поверхности.

Комментарии ?

Теорема дискретной униформизации

Теперь, когда мы можем построить упаковки окружностей поверхностей с краем, давайте обратимся к триангуляциям топологического открытого диска. Мы увидим, что есть два возможных поведения.

Параболический случай: Рассмотрим триангуляцию $T$ плоскости ${\Bbb C}$, в которой каждая вершина имеет шесть соседей.

В этом случае мы будем рассматривать набор вложенных подтриангуляций $T_k$, каждая из которых триангулирует поверхность с краем и объединением которых является поверхность $S$.

Например, вот такой набор для триангуляции выше:

Поскольку эти поверхности имеют границы, к ним применимо наше предыдущее обсуждение. Выбрав вершину $v_0$ в $T_1$ и соседа $v_1$, найдите максимальную окружность, упаковывающую $P_k$ в гиперболической плоскости для каждого $T_k$. Расположите окружности так, чтобы $C_0$, окружность, связанная с $v_0$, находилась в центре начала координат, а $C_1$, окружность, связанная с $v_1$, была ориентирована, скажем, вдоль горизонтальной оси. На рисунках ниже мы выделили кружок $C_0$.

Обратите внимание, что радиус $C_0$ приближается к нулю, когда $k$ стремится к бесконечности. На самом деле оказывается, что радиусы всех окружностей стремятся к нулю.

Равномерно масштабируем круги в каждой упаковке так, чтобы радиус $C_0$ был одинаковым в каждой упаковке. Наложение этих уплотнений друг на друга,

мы видим, что упаковки будут сходиться к обычной гексагональной пенни-упаковке на плоскости. Это максимальная упаковка ${\cal P}_T$ гексагональной триангуляции в плоскости ${\Bbb C}$.

Этот пример иллюстрирует общее явление: всякий раз, когда радиус $C_0$ стремится к нулю при стремлении $k$ к бесконечности, мы можем таким образом создать упаковку ${\cal P}_T$, которая заполняет всю плоскость ${\Bbb C }$. В этом случае мы говорим, что $T$ является параболической триангуляцией.

Гиперболический случай: Для сравнения рассмотрим открытый диск, триангулированный так, что каждая вершина имеет семь соседей:

Выбираем вложенный набор триангуляций

и найти их упаковки кругов в гиперболической плоскости.

В этом случае мы находим, что радиусы окружностей $C_0$ как бы сходятся к положительному значению, и упаковки действительно сходятся к упаковке ${\cal P}_T$, которую мы называем максимальной.

Это иллюстрирует явление, дополнительное к параболическому случаю. Всякий раз, когда радиусы окружностей $C_0$ сходятся к положительному значению, упаковки окружностей сходятся к максимальной упаковке в гиперболической плоскости ${\Bbb D}$. Назовем такую ​​триангуляцию гиперболический.

Теорема о дискретной униформизации: Эти примеры иллюстрируют тот факт, что мы можем классифицировать триангуляцию открытого диска либо как параболическую, и в этом случае ее максимальная упаковка заполняет евклидову плоскость ${\Bbb C}$, либо как гиперболическую, и в этом случае его максимальная упаковка заполняет гиперболическую плоскость ${\Bbb D}$.

Мы не обсуждали упаковки, возникающие из триангуляций двумерной сферы. Однако относительно легко увидеть, что такая триангуляция дает упаковку ${\cal P}_T$, которая заполняет сферу Римана ${\Bbb P}$. Это приводит к

Теорема о дискретной униформизации: Триангуляция $T$ односвязной поверхности без края допускает упаковку ${\cal P}_T$ поверхности $T$, которая заполняет либо евклидову плоскость ${\Bbb C}$, либо гиперболическую плоскости ${\Bbb D}$ или сфере Римана ${\Bbb P}$.

Эта теорема об упаковке кругов является аналогом теоремы об униформизации для римановых поверхностей:

Теорема об униформизации: Односвязная риманова поверхность конформно эквивалентна либо евклидовой плоскости $\Bbb C$, либо гиперболической плоскости $\Bbb D$, либо римановой сфере $\Bbb D$.

Комментарии ?

Дискретные аналитические функции

Если комплексная функция $f$ аналитична в точке $z_0$, то $f$ приблизительно линейна вблизи точки $z_0$:

$$f(z_0+z) \ приблизительно f(z_0) + f'(z_0)(z-z_0)$$

или

$$ \Delta f \приблизительно f'(z_0)\Delta z.$$

Для комплексного числа $m$ умножение $z$ на $m$ имеет простую геометрическую интерпретацию: $mz$ получается растяжением $z$ по модулю в $|m|$ и поворотом $z$ на аргумент $m$. Это означает, что функция $z\mapsto mz$ растягивает и поворачивает комплексную плоскость.

Аналитические функции локально представляются умножением на производную $f'(z_0)$; в малом масштабе вблизи $z_0$, поэтому функция $f$ растягивает и поворачивает плоскость. 92$-самолет. В этом масштабе сетка изогнута и скручена.

Однако, если мы посмотрим в небольшом масштабе вблизи точки, мы увидим, что $f$ просто растягивает и вращает сетку. В частности, это означает, что аналитическая функция переводит маленькие круги в маленькие круги.

Давайте теперь вернемся к триангуляции, которую мы рассмотрели ранее

и две различные упаковки кругов, заданные двумя наборами граничных радиусов.

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

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

Чтобы проиллюстрировать, мы можем использовать такие функции для построения аналитических карт. Например, теорема об отображении Римана утверждает, что

Если $S$ — односвязное открытое собственное подмножество плоскости, то существует обратимая аналитическая функция $f:S\to {\Bbb D}$, обратная которой также является аналитической.

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

Упаковки кругов и дискретные аналитические функции позволяют построить функцию $f$.

Для начала рассмотрим ограниченную односвязную открытую область $S$, как показано ниже. Выберем число $r>0$ и построим в плоскости шестиугольную пенни-упаковку, в которой каждая окружность имеет радиус $r$.

Теперь удалите окружности, центры которых лежат вне $S$, чтобы получить окружность, упаковывающую $P_r$.

Носителем $P_r$ является триангуляция $T_r$ поверхности с краем. Обозначим одну из окружностей в $P_r$ через $C_0$ и выберем точку $p$ внутри $C_0$. Пусть $C_1$ — лепесток, скажем, справа от $C_0$ в $P_r$. Будем называть $Q_r$ максимальной упаковкой $T_r$ в круге ${\Bbb D}$, где центр окружности, соответствующей $C_0$, находится в начале координат, а центр $C_1$ проходит вдоль горизонтальной оси. .

Это определяет дискретную аналитическую функцию $f_r:P_r\to Q_r$. Мы можем повторить этот процесс с последовательностью $r_n$, где $r_n\to 0$.

$r = 0,2$
	$\stackrel{f_{0.2}}{\longrightarrow}$
$r = 0,1$
	$\stackrel{f_{0.1}}{\longrightarrow}$
$r = 0,05$
	$\stackrel{f_{0. 05}}{\longrightarrow}$
$r = 0,025$
	$\stackrel{f_{0,025}}{\longrightarrow}$

Руководствуясь наблюдениями о том, что дискретные аналитические функции переводят окружности в окружности и что окружности в $P_r$ и $Q_r$ становятся все меньше, разумно ожидать, что дискретные аналитические функции $f_r:P_r\to Q_r$ аппроксимируют аналитическую функцию $f:S\to {\Bbb D}$ описывается теоремой Римана об отображении. Фактически, это содержание теоремы Родена-Салливана, первоначально выдвинутой Тёрстоном:0003

При $r\to0$ функции $f_r$ сходятся к отображению Римана $f$ равномерно на компактных подмножествах.

Резюме

Мы только что прикоснулись к красоте дискретных аналитических функций; дальнейшее исследование обнаруживает много аналогий с классическими аналитическими функциями.

Например, мы видели ранее, что параболическая триангуляция не может быть упакована в круг ${\Bbb D}$. Это может напомнить вам о классическом Теорема Лиувилля . Если вспомнить, что целая функция является аналитической функцией, определенной на всей комплексной плоскости, теорема Лиувилля утверждает

Теорема Лиувилля: Не существует ограниченных целых функций, которые не были бы постоянными.

По аналогии рассмотрим параболическую триангуляцию $T$ с максимальной упаковкой ${\cal P}_T$. Мы говорим, что дискретная аналитическая функция $f:{\cal P}_T\to P$ является целой, если $P$ является упаковкой в ​​${\Bbb C}$, евклидовой плоскости. Дискретная теорема Лиувилля утверждает

Дискретная Теорема Лиувилля: Не существует ограниченных дискретных целых функций.

Классическая теорема Литтла Пикара расширяет теорему Лиувилля немного дальше:

Теорема Литтла Пикара: Образ целой функции $f:{\Bbb C}\to{\Bbb C}$ не совпадает не более чем с одной точкой плоскости ${\Bbb C}$.

Существует также дискретный аналог, который остается в силе, если мы предположим, по крайней мере пока, что параболическая триангуляция $T$ является шестиугольной триангуляцией $H$ плоскости.

Дискретная теорема Пикара: Дискретная целая функция $f:{\cal P}_H\to P$ не совпадает не более чем с одной точкой плоскости ${\Bbb C}$.

Существование упаковок кругов на сфере было впервые доказано Кёбе в 1936 г., а затем независимо Андреевым и Терстоном. Фактически, использование Терстоном упаковок кругов в его работе над геометрическими 3-многообразиями является причиной того серьезного внимания, которое в последнее время уделяется упаковкам кругов.

Помимо присущего им математического интереса, упаковки кругов нашли практическое применение в самых разных приложениях, включая «уплощение мозга» — процесс создания плоских карт сильно запутанной поверхности трехмерного мозга.

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

Комментарии ?

Каталожные номера

• Кеннет Стефенсон. Введение в круговую упаковку. Издательство Кембриджского университета. 2005.

  Как следует из названия, эта книга — хорошее место для начала изучения упаковок кругов и включает в себя обширную библиографию.

• Кеннет Стефенсон. Circle Pack, бесплатное программное обеспечение для упаковки кругов.

  Я написал свои собственные программы для создания изображений, описанных в этой статье, но CirclePack намного мощнее и стабильнее. Я модифицировал один из комплексов, включенных в CirclePack, и использовал его для создания некоторых изображений.

• Уильям Терстон. Геометрия и топология трехмерных многообразий. Доступно по адресу http://library.msri.org/books/gt3m/.

  Основополагающие заметки Терстона, в которых, среди прочего, излагается его гипотеза геометризации для трехмерных многообразий. Эти заметки впервые появились в мимеографической форме, распространяемой Принстонским университетом. Первые несколько глав были отредактированы Сильвио Леви и впоследствии появились в виде книги, доступной в Princeton University Press по ссылке выше.

• Чарльз Коллинз и Кеннет Стивенсон. Алгоритм упаковки кругов. Вычислительная геометрия, 25, стр. 223-256, 2003.

  В этой статье описывается эффективный алгоритм создания упаковок кругов.

• Тристан Нидхэм. Зрительный комплексный анализ. Издательство Оксфордского университета. 1997.


• Страницы Википедии, посвященные теореме об отображении Римана и теореме об униформизации.