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

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

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

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

Уникальность [ править ]

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

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

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

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

Отношения с теорией конформных отображений [ править ]

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

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

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

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

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

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

Доказательства [ править ]

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

Приложения [ править ]

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

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

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

Алгоритмические аспекты [ править ]

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

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

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

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

Обобщения [ править ]

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

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

Еще одна разновидность обобщений допускает формы, не являющиеся кругами. Предположим , что G  = ( V ,  E ) является конечной плоский граф, и каждая вершина v из G соответствует форму , которая гомеоморфно замкнутому единичному диску и граница которой является гладкой. Тогда существует такая упаковка на плоскости, что тогда и только тогда и для каждого набор получается из${\ Displaystyle К_ {v} \ подмножество \ 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-регулярные плоские графы
• Круги Форда , упаковка кругов по линии рациональных чисел
• Граф Пенни , графы монет, окружности которых имеют одинаковый радиус
• Лемма о кольце , оценка размеров соседних окружностей в упаковке

Заметки [ править ]

Ссылки [ править ]

• Андреев Е.М. (1970), "Выпуклые многогранники в пространствах Лобачевского", Матем. Сб. (NS) , 81 (123): 445–478, MR  0259734.
• Бирдон, Алан Ф .; Стивенсон, Кеннет (1990), "Теорема униформизации для кольцевых упаковок" , Indiana Univ. Математика. J. , 39 : 1383–1425
• Бирдон, Алан Ф .; Стивенсон, Кеннет (1991), "Лемма Шварца-Пика для упаковки кругов" , Illinois J. Math. , 35 : 577–606
• Андреев Е.М. (1970), "Выпуклые многогранники конечного объема в пространстве Лобачевского", Матем. Сб. (NS) , 83 (125): 256–260, MR  0273510.
• Бенджамини, Итаи ; Schramm, Oded (2001), "Повторяемость пределов распределения конечных плоских графов" , Electronic Journal of Probability , 6 , MR  1873300.
• Брандт, М. (1980), "Ein Abbildungssatz fur endlich-vielfach zusammenhangende Gebiete", Bull. de la Soc. des Sc. et des Lettr. де Лодзь , 30.
• Brightwell, Graham R .; Шайнерман, Эдвард Р. (1993), "Представления плоских графов", SIAM J. Discrete Math. , 6 (2): 214-229, DOI : 10,1137 / 0406017.
• Картер, Итиэль; Родин, Берт (1992), "Обратная задача для упаковки кругов и конформного отображения" , Пер. Амер. Математика. Soc. , 334 : 861–875
• Колин де Вердьер, Ив (1991), "Une principe changenel pour les empilements de cercles", Inventiones Mathematicae , 104 (1): 655–669, Bibcode : 1991InMat.104..655C , doi : 10.1007 / BF01245096.
• Коллинз, Чарльз Р .; Стивенсон, Кеннет (2003), "Алгоритм упаковки кругов", Вычислительная геометрия. Теория и приложения , 25 (3): 233-256, DOI : 10.1016 / S0925-7721 (02) 00099-8 , МР  1975216.
• Харрингтон, Эндрю Н. (1982), «Конформные отображения на области с произвольно заданной формой границ», Journal d'Analyse Mathématique , 41 (1): 39–53, doi : 10.1007 / BF02803393
• Йоннасон, Йохан; Schramm, Oded (2000), "О времени покрытия плоских графов" , Electronic Communications in Probability , 5 : 85–90..
• Кельнер, Джонатан А. (2006), "Спектральное разделение, на собственные значения оценки, и круг упаковка для графов ограниченного рода", SIAM журнал по вычислениям , 35 (4): 882-902, DOI : 10,1137 / S0097539705447244 , ЛВП : 1721,1 / 30169.
• Кесег, Балаж; Пах, Янош ; Pálvölgyi, Dömötör (2011), «Рисование плоских графов ограниченной степени с небольшими наклонами», Брандес, Ульрик; Корнельсен, Сабина (ред.), Рисование графиков: 18-й Международный симпозиум, GD 2010, Констанц, Германия, 21-24 сентября 2010 г., Revised Selected Papers , Lecture Notes in Computer Science, 6502 , Heidelberg: Springer, pp. 293–304 , Arxiv : 1009.1315 , DOI : 10.1007 / 978-3-642-18469-7_27 , МР  2781274.
• Koebe, Paul (1936), "Kontaktprobleme der Konformen Abbildung", Ber. Sächs. Акад. Wiss. Лейпциг, Math.-Phys. Kl. , 88 : 141–164.
• Липтон, Ричард Дж .; Тарьян, Роберт Е. (1979), "Теорема Сепаратор для плоских графов", SIAM журнал по прикладной математике , 36 : 177-189, CiteSeerX  10.1.1.104.6528 , DOI : 10,1137 / 0136016.
• Малиц, Сет; Papakostas, Ахиллеас (1994), "О угловом разрешении плоских графов", SIAM Journal по дискретной математике , 7 (2): 172-183, DOI : 10,1137 / S0895480193242931 , МР  1271989.
• Миллер, Гэри Л .; Тэн, Шан-Хуа ; Терстон, Уильям ; Вавасис, Стивен А. (1997), "Разделители для сфер-упаковок и графов ближайших соседей", J. ACM , 44 (1): 1–29, DOI : 10.1145 / 256292.256294.
• Мохар, Боян (1993), "Алгоритм упаковки кругов с полиномиальным временем", Дискретная математика , 117 (1–3): 257–263, DOI : 10.1016 / 0012-365X (93) 90340-Y.
• Родин, Бертон ; Салливан, Деннис (1987), "Сходимость упаковок кругов к отображению Римана" , Журнал дифференциальной геометрии , 26 (2): 349–360.
• Роде, Штеффен (2011), «Одед Шрамм: от упаковки кругов к SLE» , Ann. Вероятно. , 39 : 1621–1667
• Стефенсон, Кеннет (1999), "Аппроксимация конформных структур посредством упаковки кругов" (PDF) , Вычислительные методы и теория функций 1997 (Никосия) , сер. Прибл. Разл., 11 , Мировая наука. Publ., River Edge, NJ, стр. 551–582, MR  1700374.
• Стивенсон, Кен (2003), «Упаковка кругов: математическая сказка» (PDF) , Notices Amer. Математика. Soc. , 50 : 1376–1388
• Стивенсон, Кен (2005), Введение в упаковку кругов, теорию дискретных аналитических функций , Кембридж: Издательство Кембриджского университета..
• Терстон, Уильям (1985), Теорема о конечном отображении Римана , Приглашенный доклад на Международном симпозиуме в Университете Пердью по случаю доказательства гипотезы Бибербаха.
• Терстон, Уильям (1978–1981), Геометрия и топология трехмерных многообразий , Примечания к лекциям в Принстоне.

Внешние ссылки [ править ]

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