Теорема об упаковке кругов

«Граф монет» перенаправляется сюда. Контактные графы дисков равного радиуса см. в «Пенни-графике» .

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

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

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

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

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

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

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

Существует также более элементарное доказательство того же свойства единственности, основанное на существовании максимального значения в любом конечном множестве и на наблюдении, что в треугольнике, соединяющем центры трех взаимно касающихся окружностей, угол, образованный в центре одной кругов монотонно убывает по своему радиусу и монотонно возрастает по двум другим радиусам. Даны две упаковки для одного и того же графа $G$, можно применить отражения и преобразования Мёбиуса, чтобы внешние круги в этих двух упаковках соответствовали друг другу и имели одинаковые радиусы. Тогда пусть $v$ быть внутренней вершиной $G$ для которого окружности в двух упаковках имеют размеры как можно дальше друг от друга: т. е. выберем $v$ чтобы максимизировать соотношение $r_{1}/r_{2}$ радиусов его окружностей в двух упаковках. Для каждой треугольной грани $G$ содержащий $v$, отсюда следует, что угол в центре окружности для $v$ в первой упаковке меньше или равен углу во второй упаковке, причем равенство возможно только тогда, когда два других круга, образующие треугольник, имеют одинаковое соотношение $r_{1}/r_{2}$ радиусов в двух упаковках. Но сумма углов всех этих треугольников, окружающих центр треугольника, должна быть равна $2\pi$ в обеих упаковках, поэтому все соседние вершины $v$ должно иметь то же соотношение, что и $v$ сам. Если поочередно применить тот же аргумент к этим другим кругам, то из этого следует, что все круги в обеих упаковках имеют одинаковое соотношение. Но внешние круги были преобразованы, чтобы иметь соотношение один, поэтому $r_{1}/r_{2}=1$ и обе упаковки имеют одинаковые радиусы для всех кругов.

Отношения с конформной теорией отображений

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

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

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

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

Гипотеза Терстона была доказана Роденом и Салливаном (1987) . Точнее, они показали, что при стремлении n к бесконечности функция fn _, определенная с помощью метода Терстона из гексагональных упаковок окружностей радиуса 1/ n, равномерно на компактных подмножествах A к конформному отображению из A в C. сходится

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

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

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

Приложения

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

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

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

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

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

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

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

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

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

Обобщения

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

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

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

История

Упаковки кругов были изучены еще в 1910 году в работе Арнольда Эмча о спиралях Дойла в филлотаксисе (математике роста растений). Теорема об упаковке кругов была впервые доказана Полом Кебе . Уильям Терстон заново открыл теорему об упаковке кругов иотметил, что это следует из работы Е.М. Андреева . Терстон также предложил схему использования теоремы об упаковке кругов для получения гомеоморфизма односвязного собственного подмножества плоскости на внутреннюю часть единичного круга. Гипотеза Тёрстона об упаковках кругов — это его гипотеза о том, что гомеоморфизм будет сходиться к отображению Римана , когда радиусы окружностей стремятся к нулю. Гипотеза Тёрстона позже была доказана.Бертон Роден и Деннис Салливан . Это привело к шквалу исследований расширений теоремы об упаковке кругов, связей сконформные отображения и приложения.

См. также

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

Ссылки

• Андреев Е. М. (1970), "Выпуклые многогранники в пространствах Лобачевского", Матем. Сб. , Новая серия, 81 (123): 445–478, Bibcode : 1970SbMat..10..413A , doi : 10.1070/SM1970v010n03ABEH001677 , MR   0259734 .
• Бердон, Алан Ф.; Стивенсон, Кеннет (1990), «Теорема униформизации для круговых упаковок» , Университет Индианы. Математика. J. , 39 (4): 1383–1425, номер документа : 10.1512/iumj.1990.39.39062.
• Бердон, Алан Ф.; Стивенсон, Кеннет (1991), «Лемма Шварца-Пика для упаковок кругов» , Illinois J. Math. , 35 (4): 577–606, doi : 10.1215/ijm/1255987673
• Андреев Е. М. (1970), "Выпуклые многогранники конечного объема в пространстве Лобачевского", Матем. Сб. , Новая серия, 83 (125): 256–260, Бибкод : 1970SbMat..12..255A , doi : 10.1070/SM1970v012n02ABEH000920 , MR   0273510 .
• Бенджамини, Итай ; Шрамм, Одед (2001), «Повторяемость пределов распределения конечных плоских графов» , Электронный журнал вероятностей , 6 , doi : 10.1214/EJP.v6-96 , MR   1873300 , S2CID   2862151 .
• Брандт, М. (1980), «Теорема об отображении для конечно-кратно связных регионов», De la Soc. Дес. И дез Леттр. Де Лодзь , 30 .
• Брайтвелл, Грэм Р.; Шайнерман, Эдвард Р. (1993), «Представления плоских графов», SIAM J. Discrete Math. , 6 (2): 214–229, doi : 10.1137/0406017 .
• Картер, Итиэль; Роден, Берт (1992), «Обратная задача для упаковки кругов и конформного отображения» , Trans. амер. Математика. Соц. , 334 (2): 861–875, doi : 10.1090/S0002-9947-1992-1081937-X
• Колин де Вердьер, Ив (1991), «Вариационный принцип для стопок кругов», Inventiones Mathematicae , 104 (1): 655–669, Bibcode : 1991InMat.104..655C , doi : 10.1007/BF01245096 , S2CID   121028882 .
• Коллинз, Чарльз Р.; Стивенсон, Кеннет (2003), «Алгоритм упаковки кругов», Вычислительная геометрия. Теория и приложения , 25 (3): 233–256, doi : 10.1016/S0925-7721(02)00099-8 , MR   1975216 .
• Харрингтон, Эндрю Н. (1982), «Конформные отображения на области с произвольно заданной формой границ», Journal d'Analyse Mathématique , 41 (1): 39–53, doi : 10.1007/BF02803393 , S2CID   120752035
• Йоннасон, Йохан; Шрамм, Одед (2000), «О времени покрытия плоских графов» , Electronic Communications in Probability , 5 : 85–90 .
• Келнер, Джонатан А. (2006), «Спектральное разбиение, границы собственных значений и упаковки кругов для графов ограниченного рода», SIAM Journal on Computing , 35 (4): 882–902, doi : 10.1137/S0097539705447244 , hdl : 1721.1/ 30169 .
• Кесег, Балаж; Пах, Янош ; Палвёлдьи, Дёмётёр (2011), «Рисование плоских графов ограниченной степени с небольшим количеством наклонов», в Брандесе, Ульрике ; Корнельсен, Сабина (ред.), Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21–24 сентября 2010 г., Пересмотренные избранные статьи , Конспекты лекций по информатике, том. 6502, Гейдельберг: Springer, стр. 293–304, arXiv : 1009.1315 , doi : 10.1007/978-3-642-18469-7_27 , MR   2781274 , S2CID   817874 .
• Кобе, Пол (1936), «Контактные проблемы конформного отображения», Бер. Саксонский. Академическая наука Лейпциг, Матем.-Физ. кл. , 88 : 141–164 .
• Липтон, Ричард Дж .; Тарьян, Роберт Э. (1979), «Теорема о разделителе для плоских графов», SIAM Journal on Applied Mathematics , 36 (2): 177–189, CiteSeerX   10.1.1.104.6528 , doi : 10.1137/0136016 .
• Малиц, Сет; Папакостас, Ахиллеас (1994), «Об угловом разрешении плоских графов», SIAM Journal on Discrete Mathematics , 7 (2): 172–183, doi : 10.1137/S0895480193242931 , MR   1271989 .
• Миллер, Гэри Л .; Тэн, Шанхуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997), «Сепараторы для сферических упаковок и графов ближайших соседей», J. ACM , 44 (1): 1–29, doi : 10.1145/256292.256294 , S2CID   17331739 .
• Мохар, Боян (1993), «Алгоритм упаковки полиномиального временного круга», Discrete Mathematics , 117 (1–3): 257–263, doi : 10.1016/0012-365X(93)90340-Y .
• Роден, Бертон ; Салливан, Деннис (1987), «Сходимость упаковок кругов к отображению Римана» , Журнал дифференциальной геометрии , 26 (2): 349–360, doi : 10.4310/jdg/1214441375 .
• Роде, Штеффен (2011), «Одед Шрамм: от упаковки кругов до СКВ» , Ann. Вероятно. , 39 (5): 1621–1667, arXiv : 1007.2007 , doi : 10.1214/10-AOP590.
• Стивенсон, Кеннет (1999), «Приближение конформных структур с помощью упаковки кругов» (PDF) , Вычислительные методы и теория функций 1997 (Никосия) , Сер. Прибл. Разлагается., т. 1, с. 11, Мировая наука. Publ., Ривер Эдж, Нью-Джерси, стр. 551–582, MR   1700374 .
• Стивенсон, Кен (2003), «Упаковка кругов: математическая сказка» (PDF) , Notes Amer. Математика. Соц. , 50 : 1376–1388
• Стивенсон, Кен (2005), Введение в упаковку кругов, теория дискретных аналитических функций , Кембридж: Издательство Кембриджского университета .
• Терстон, Уильям (1985), Теорема о конечном отображении Римана , Приглашенный доклад на Международном симпозиуме в Университете Пердью по случаю доказательства гипотезы Бибербаха .
• Терстон, Уильям (1978–1981), Геометрия и топология трехмерных многообразий , конспект лекций в Принстоне .

Внешние ссылки

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