Теорема об упаковке круга - Circle packing theorem

Упаковка кругов для плоского графа с пятью вершинами

В теорема об упаковке кругов (также известный как Теорема Кебе – Андреева – Терстона.) описывает возможные отношения касания между окружностями на плоскости, внутренности которых не пересекаются. А упаковка круга является связным набором окружностей (вообще говоря, на любой римановой поверхности), внутренности которых не пересекаются. В граф пересечений упаковки кругов - это граф, имеющий вершина для каждого круга и край для каждой пары кругов, которые касательная. Если упаковка кругов находится на плоскости или, что то же самое, на сфере, то ее граф пересечений называется график монет; в более общем смысле, графы пересечений внутренне непересекающихся геометрических объектов называются графики касания или же графики контактов. Графики монет всегда связаны, просто, и планарный. Теорема об упаковке кругов утверждает, что это единственные требования, чтобы граф был графом монет:

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

Уникальность

А максимальный планарный граф грамм представляет собой конечный простой планарный граф, к которому нельзя добавить ребер при сохранении планарности. Такой граф всегда имеет единственное плоское вложение, в котором каждая грань вложения (включая внешнюю грань) является треугольником. Другими словами, каждый максимальный планарный граф грамм является 1-скелетом симплициальный комплекс который гомеоморфный в сферу. Теорема об упаковке кругов гарантирует существование упаковки с конечным числом окружностей, граф пересечений которой изоморфен грамм. Как формулирует следующая теорема, каждый максимальный планарный граф может иметь не более одной упаковки.

Теорема Кебе – Андреева – Терстона.: Если грамм - конечный максимальный планарный граф, то упаковка окружностей, граф касания которой изоморфен грамм уникален, вплоть до Преобразования Мебиуса и отражения в линиях.

Терстон^[1] отмечает, что эта уникальность является следствием Теорема жесткости Мостова. Чтобы увидеть это, позвольте грамм быть изображенным в виде упаковки круга. Тогда плоскость, в которой упакованы круги, можно рассматривать как границу модель полупространства для трехмерного гиперболическое пространство; с этой точки зрения каждый круг является границей плоскости в гиперболическом пространстве. Таким образом, можно определить набор непересекающихся плоскостей из окружностей упаковки, а второй набор непересекающихся плоскостей определяется окружностями, которые ограничивать каждый треугольный зазор между тремя кружками в упаковке. Эти два набора плоскостей встречаются под прямым углом и образуют генераторы из группа отражения чей фундаментальная область можно рассматривать как гиперболическое многообразие. По жесткости Мостова гиперболическая структура этой области определяется однозначно с точностью до изометрия гиперболического пространства; эти изометрии, если рассматривать их с точки зрения их действия на евклидовой плоскости на границе модели полуплоскости, переводятся в преобразования Мёбиуса.

Существует также более элементарное доказательство того же свойства уникальности, основанное на принцип максимума и на наблюдении, что в треугольнике, соединяющем центры трех взаимно касательных окружностей, угол, образованный в центре одной из окружностей, монотонно уменьшается по радиусу и монотонно увеличивается по двум другим радиусам. Учитывая две упаковки для одного и того же графа граммможно применить отражения и преобразования Мёбиуса, чтобы внешние круги в этих двух упаковках соответствовали друг другу и имели одинаковые радиусы. Тогда пусть v быть внутренней вершиной грамм для которых круги в двух упаковках имеют размеры, максимально удаленные друг от друга: т. е. выберите v чтобы максимизировать соотношение р₁/р₂ радиусов его окружностей в двух упаковках. Для каждой треугольной грани грамм содержащий v, следует, что угол в центре окружности при v в первой упаковке меньше или равен углу во второй упаковке, причем равенство возможно только тогда, когда два других круга, образующих треугольник, имеют такое же отношение р₁/р₂ радиусов в двух упаковках. Но сумма углов всех этих треугольников, окружающих центр треугольника, должна быть 2π в обеих упаковках, поэтому все соседние вершины должны быть v должен иметь такое же соотношение, как v сам. Применяя тот же аргумент к этим другим кругам по очереди, следует, что все круги в обеих упаковках имеют одинаковое соотношение. Но внешние круги были преобразованы, чтобы иметь отношение 1, поэтому р₁/р₂ = 1, и две упаковки имеют одинаковые радиусы для всех окружностей.

Связь с теорией конформных отображений

Упаковки кругов можно использовать для аппроксимации конформных отображений между указанными доменами. Каждый кружок слева соответствует кружку справа.

А конформная карта между двумя открытые наборы на плоскости или в многомерном пространстве - это непрерывная функция от одного набора к другому, что сохраняет углы между любыми двумя кривыми. В Теорема римана отображения, сформулированный Бернхард Риманн в 1851 г., утверждает, что для любых двух открытых топологические диски на плоскости есть конформное отображение одного диска на другой. Конформные отображения находят применение в создание сетки, картографическая проекция, и другие области. Однако не всегда легко построить конформное отображение между двумя заданными областями явным образом.^[2]

На конференции в Бибербахе в 1985 г. Уильям Терстон предположил, что упаковки кругов можно использовать для аппроксимации конформных отображений. Точнее, Терстон использовал упаковки кругов, чтобы найти конформное отображение произвольного открытого диска. А внутрь круга; отображение из одного топологического диска А на другой диск B затем можно найти, составив карту из А в круг с обратной картой из B в круг.^[2]

Идея Терстона заключалась в том, чтобы упаковать круги небольшого радиуса. р в шестиугольнике мозаика самолета, в пределах региона А, оставляя узкую область вблизи границы А, шириной р, где больше не могут поместиться круги с таким радиусом. Затем он строит максимальный планарный граф грамм от граф пересечений окружностей вместе с одной дополнительной вершиной, примыкающей ко всем окружностям на границе упаковки. По теореме об упаковке кругов этот плоский граф может быть представлен упаковкой кругов C в котором все ребра (включая инцидентные граничной вершине) представлены касаниями окружностей. Кружки из упаковки А взаимно однозначно соответствуют кружкам из C, кроме граничного круга C что соответствует границе А. Это соответствие окружностей можно использовать для построения непрерывной функции из А к C в котором каждый круг и каждый промежуток между тремя кругами отображаются от одной упаковки к другой с помощью Преобразование Мёбиуса. Терстон предположил, что в пределе радиуса р стремится к нулю, функции из А к C построенный таким образом, приблизился бы к конформной функции, заданной теоремой Римана об отображении.^[2]

Гипотеза Терстона была доказана Родин и Салливан (1987). Точнее, они показали, что, как п уходит в бесконечность, функция ж_п определяется методом Терстона из гексагональных упаковок радиуса -1 /п окружности сходятся равномерно на компактных подмножествах А на конформную карту из А к C.^[2]

Несмотря на успех гипотезы Терстона, практические применения этого метода были затруднены из-за сложности вычисления круговых упаковок и его относительно низкой скорости сходимости. Однако он имеет некоторые преимущества при применении к не-односвязный областей и при выборе начальных приближений для численных методов, которые вычисляют Отображения Шварца – Кристоффеля, другой метод конформного отображения многоугольный домены.^[2]

Доказательства

Существует множество известных доказательств теоремы об упаковке кругов. Пол Кобе Оригинальное доказательство основано на его теореме о конформной униформизации, в которой говорится, что конечносвязная плоская область конформно эквивалентна круговой области. Известно несколько различных топологических доказательств. Доказательство Терстона основано на Теорема Брауэра о неподвижной точке. Будучи аспирантом, Одед Шрамм находился под наблюдением Терстона в Университет Принстона. В качестве Роде (2011 г., п. 1628), в диссертации Шрамма есть «поэтическое описание» того, как существование упаковки кругов может быть выведено из теоремы о неподвижной точке: «Можно просто увидеть ужасного монстра, размахивающего руками в явной ярости, щупальца которого издают ужасное шипение. , поскольку они трутся друг о друга ". Также есть доказательство с использованием дискретного варианта Метод Перрона построения решенийЗадача Дирихле.^[3] Ив Колен де Вердьер доказал существование упаковки кругов как минимизатора выпуклая функция в определенном пространстве конфигурации.^[4]

Приложения

Теорема об упаковке кругов - полезный инструмент для изучения различных проблем плоской геометрии, конформных отображений и планарных графов. Элегантное доказательство теорема о плоском сепараторе, первоначально из-за Липтона и Тарьяна,^[5] был получен таким образом.^[6]Другое применение теоремы об упаковке кругов состоит в том, что несмещенные пределы плоских графов ограниченной степени почти наверняка рекуррентны.^[7]Другие приложения включают последствия для время покрытия.^[8]и оценки крупнейших собственное значение ограниченногород графики.^[9]

В рисунок графика, упаковка кругов использовалась для поиска чертежей планарных графов с ограниченными угловое разрешение^[10] и с ограниченным номер откоса.^[11]Теорема Фари, что каждый граф, который может быть нарисованный без пересечений в плоскости с помощью криволинейных кромок также можно рисовать без пересечений с помощью прямых отрезок ребер, следует как простое следствие теоремы об упаковке окружностей: помещая вершины в центры окружностей и проводя прямые ребра между ними, получается прямолинейное плоское вложение.

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

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

Алгоритмические аспекты

Коллинз и Стивенсон (2003) описать числовой алгоритм релаксации для поиска круговых упаковок, основанных на идеях Уильям Терстон. Версия проблемы упаковки кругов, которую они решают, принимает на вход планарный граф, в котором все внутренние грани являются треугольниками, а внешние вершины помечены положительными числами. На выходе он производит упаковку окружностей, касания которой представляют данный граф, а окружности, представляющие внешние вершины, имеют радиусы, указанные во входных данных. По их мнению, ключ к решению проблемы - сначала вычислить радиусы окружностей в упаковке; как только радиусы известны, геометрическое положение окружностей вычислить несложно. Они начинаются с набора предварительных радиусов, которые не соответствуют допустимой упаковке, а затем повторно выполняются следующие шаги:

Выберите внутреннюю вершину v входного графа.
Вычислите полный угол θ, который k соседние круги будут покрывать круг на v, если бы соседи были размещены касательными друг к другу и к центральной окружности с использованием их ориентировочных радиусов.
Определите репрезентативный радиус р для соседних окружностей, таких что k круги радиуса р дадут тот же угол покрытия θ, что и соседи v дайте.
Установите новый радиус для v быть ценностью, для которой k круги радиуса р даст угол покрытия ровно 2π.

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

Мохар (1993) описывает аналогичный итерационный метод поиска одновременных упаковок многогранный граф и его дуальный, в котором дуальные круги расположены под прямым углом к первичным окружностям. Он доказывает, что для этого метода требуется время, полиномиальное по количеству кругов и log 1 / ε, где ε - это граница расстояния центров и радиусов вычисленной упаковки от центров оптимальной упаковки.

Обобщения

Теорема об упаковке кругов обобщается на графы, которые не являются планарными. грамм это граф, который можно вложить в поверхность S, то существует постоянная кривизна Риманова метрика d на S и круглая упаковка на (S, d), граф контактов которого изоморфен грамм. Если S закрыто (компактный и без граница )и грамм это триангуляция S, тогда (S, d) и упаковка единственны с точностью до конформной эквивалентности. Если S - сфера, то эта эквивалентность с точностью до преобразований Мёбиуса; если это тор, то эквивалентность сводится к масштабированию с помощью константы и изометрий, а если S имеет род не менее 2, то эквивалентность с точностью до изометрий.

Другое обобщение теоремы об упаковке окружностей включает замену условия касания заданным углом пересечения окружностей, соответствующих соседним вершинам. Особенно элегантная версия выглядит следующим образом. Предположим, что грамм конечный 3-связный планарный граф (то есть многогранный граф ), то существует пара упаковок окружностей, граф пересечений которой изоморфен грамм, другой, граф пересечений которого изоморфен плоский двойной из грамм, и для каждой вершины в грамм и прилегающей к ней грани, круг в первой упаковке, соответствующей вершине, пересекается ортогонально с кругом во второй упаковке, соответствующей грани.^[12] Например, применение этого результата к графику тетраэдра дает для любых четырех взаимно касательных окружностей второй набор из четырех касательных друг к другу окружностей, каждая из которых ортогональна трем из первых четырех.^[13] Дальнейшее обобщение, замена угла пересечения на обратное расстояние, позволяет специфицировать упаковки, в которых требуется, чтобы некоторые окружности не пересекались друг с другом, а не касались друг друга.^[14]

Еще одна разновидность обобщений допускает формы, не являющиеся кругами. грамм = (V, E) - конечный планарный граф, и каждой вершине v из граммсоответствует форме ${ Displaystyle K_ {v} subset mathbb {R} ^ {2}}$ , который гомеоморфный к замкнутому единичному кругу, граница которого гладкая. ${ Displaystyle P = (K '_ {v}: v in V)}$ в самолетах, что ${ displaystyle K '_ {v} cap K' _ {u} neq varnothing}$ если и только если ${ displaystyle [v, u] in E}$ и для каждого ${ displaystyle v in V}$ набор ${ displaystyle K '_ {v}}$ получается из ${ displaystyle K_ {v}}$ путем перевода и масштабирования. (Обратите внимание, что в исходной теореме об упаковке круга существует три реальных параметра для каждой вершины, два из которых описывают центр соответствующей окружности, а один - радиус, и есть одно уравнение для каждого ребра. Это также верно в этом обобщении .) Одно доказательство этого обобщения может быть получено путем применения оригинального доказательства Кёбе.^[15] и теорема Брандта^[16] и Харрингтон^[17] утверждая, что любая конечносвязная область конформно эквивалентна плоской области, граничные компоненты которой имеют заданные формы, с точностью до сдвигов и масштабирования.

История

Теорема об упаковке кругов была впервые доказана Пол Кобе.^[15]Уильям Терстон^[1] заново открыл теорему об упаковке кругов и отметил, что она вытекает из работ Андреев Е. М.. Терстон также предложил схему использования теоремы об упаковке окружностей для получения гомеоморфизма односвязного собственного подмножества плоскости на внутреннюю часть единичного круга. В Гипотеза Терстона для круговых упаковок его гипотеза о том, что гомеоморфизм сходится к Отображение Римана поскольку радиусы кружков стремятся к нулю. Позднее гипотеза Терстона была доказана Бертон Родин и Деннис Салливан.^[18]Это привело к шквалу исследований расширений теоремы об упаковке кругов, связей с конформными отображениями и приложений.

Смотрите также

Аполлонийская прокладка, бесконечная упаковка, образованная многократным заполнением треугольных промежутков
Упаковка круга, плотное расположение окружностей без заданных касаний
Спирали Дойля, упаковки кругов, представляющие бесконечные 6-регулярные планарные графы
Круги Форда, упаковка кругов по прямой с рациональными числами
Пенни график, графы монет, окружности которых имеют одинаковый радиус
Лемма о кольце, оценка размеров соседних окружностей в упаковке

Примечания

^ ^а ^б Терстон (1978–1981), Гл. 13.
^ ^а ^б ^c ^d ^е Стивенсон (1999).
^ Бирдон и Стивенсон 1991, Картер и Роден 1992
^ Колин де Вердьер 1991
^ Липтон и Тарьян (1979)
^ Miller et al. (1997)
^ Бенджамини и Шрамм (2001)
^ Джоннасон и Шрамм (2000)
^ Кельнер (2006)
^ Малиц и Папакостас (1994).
^ Кесег, Пах и Палвёльдьи (2011).
^ Брайтвелл и Шайнерман (1993)
^ Кокстер, Х. С. М. (2006), "Абсолютное свойство четырех касательных друг к другу окружностей", Неевклидовы геометрии, Математика. Appl. (Н. Ю.), 581, Нью-Йорк: Springer, стр. 109–114, Дои:10.1007/0-387-29555-0_5, МИСТЕР 2191243.
^ Bowers, Philip L .; Стивенсон, Кеннет (2004), "8.2 Инверсивные дистанционные упаковки", Униформизация рисунков и карт Белого с помощью упаковки кругов, Мемуары Американского математического общества, 805, стр. 78–82, Дои:10.1090 / memo / 0805, МИСТЕР 2053391.
^ ^а ^б Кебе (1936)
^ Брандт (1980)
^ Харрингтон (1982)
^ Родин и Салливан (1987)

внешняя ссылка

CirclePack (бесплатное программное обеспечение для построения упаковок кругов из графиков) и Библиография упаковки круга Кеннета Стивенсона, Univ. Теннесси

[thu-1] а ^б Терстон (1978–1981), Гл. 13.

[s99-2] а ^б ^c ^d ^е Стивенсон (1999).

[3] Бирдон и Стивенсон 1991, Картер и Роден 1992

[4] Колин де Вердьер 1991

[5] Липтон и Тарьян (1979)

[6] Miller et al. (1997)

[7] Бенджамини и Шрамм (2001)

[8] Джоннасон и Шрамм (2000)

[9] Кельнер (2006)

[10] Малиц и Папакостас (1994).

[11] Кесег, Пах и Палвёльдьи (2011).

[12] Брайтвелл и Шайнерман (1993)

[13] Кокстер, Х. С. М. (2006), "Абсолютное свойство четырех касательных друг к другу окружностей", Неевклидовы геометрии, Математика. Appl. (Н. Ю.), 581, Нью-Йорк: Springer, стр. 109–114, Дои:10.1007/0-387-29555-0_5, МИСТЕР 2191243.

[14] Bowers, Philip L .; Стивенсон, Кеннет (2004), "8.2 Инверсивные дистанционные упаковки", Униформизация рисунков и карт Белого с помощью упаковки кругов, Мемуары Американского математического общества, 805, стр. 78–82, Дои:10.1090 / memo / 0805, МИСТЕР 2053391.

[koebe-15] а ^б Кебе (1936)

[16] Брандт (1980)

[17] Харрингтон (1982)

[18] Родин и Салливан (1987)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

Проблемы с упаковкой
Упаковка круга	По кругу / равносторонний треугольник / равнобедренный прямоугольный треугольник / квадрат Аполлонийская прокладка Теорема об упаковке круга Проблема Таммеса (на сфере)
Упаковка сфер	Аполлонический В сфере В кубе В цилиндре Плотная упаковка Целующий номер Граница упаковки сфер (Хэмминга)
Прочие упаковки	Корзина Тетраэдр Набор
Загадки	Конвей Ленивец-Граацма