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

Материал из testwiki
Перейти к навигации Перейти к поиску

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

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

Пример упаковки окружностей для K5 (полного графа с пятью вершинами) без одного ребра.

Единственность

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

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

ТёрстонШаблон:Sfn заметил, что эта единственность является следствием теоремы Мостова о жёсткости. Плоскость, в которой круги упакованы, можно рассматривать как границу модели Пуанкаре в полупространстве. С этой точки зрения, любой круг является границей плоскости в гиперболическом пространстве. Каждой упаковке кругов можно сопоставить множество непересекающихся плоскостей, а также второе множество непересекающихся плоскостей, определённых треугольными участками между тремя кругами упаковки. Плоскости из различных множеств пересекаются под прямыми углами и соответствуют генераторам Шаблон:Не переведено 5, фундаментальную область которой можно рассматривать как Шаблон:Не переведено 5. По теореме о жёсткости Мостова, гиперболическая структура этой области определена однозначно с точностью до изометрий гиперболического пространства. Эти изометрии, если рассматривать их в терминах действия на границе модели Пуанкаре, превращаются в преобразования Мёбиуса.

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

Обобщения теоремы об упаковке кругов

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

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

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

Ещё одно обобщение позволяет использовать фигуры, отличные от кругов. Предположим, что G = (V, E) является конечным планарным графом, и каждая вершина v графа G соответствует фигуре Kv⊂ℝ2, которая гомеоморфна замкнутому единичному диску и граница которой гладкая. Тогда существует упаковка P=(K'v:v∈V) на плоскости, такая что K'v∩K'u≠∅ тогда и только тогда, когда [v,u]∈E и для каждого v∈V множество K'v получается из Kv путём движения и масштабирования. (Заметим, что в исходной теореме об упаковке кругов имеется три параметра для вершины, два из которых задают центр соответствующей окружности и один задаёт радиус, и имеется одно уравнение для каждого ребра. Это выполняется и для этого обобщения.) Одно из доказательств этого обобщения можно получить путём использования исходного доказательства КоебеШаблон:Sfn и теоремы БрандтаШаблон:Sfn и ХаррингтонаШаблон:Sfn, утверждающего, что любая конечная связная область конформно эквивалентна плоской области, границы компонентов которой имеют специфичные фигуры с точностью до переноса и масштабирования.

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

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

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

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

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

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

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

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

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

Приложения теоремы упаковки кругов

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

Другие применения — выводы для времени случайного обхода графаШаблон:Sfn и оценка максимального собственного значения графов с ограниченным родом Шаблон:Sfn.

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

Файл:CirclePacking.svg
Вычисление радиуса окружности (выделена красным) радиуса r0.
На первом шаге вычисляем угол θ.
На втором шаге вычисляем усреднённый радиус rs.
На третьем шаге вычисляем исправленный радиус окружности rn

Доказательство теоремы

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

Существует также доказательство, использующее дискретный вариант Шаблон:Не переведено 5 построения решения задачи Дирихле. Ивз Колин де Вердьер (Yves Colin de Verdière) доказалШаблон:Sfn существование упаковки кругов как минимизатора выпуклой функции на некоторых пространствах конфигураций.

Следствия

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

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

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

Коллинз и Стефенсон Шаблон:Sfn описали численный Шаблон:Не переведено 5 для нахождения упаковок окружностей, основанный на идеях Уильяма Тёрстона. Версия задачи упаковки кругов, которую они решают, имеет на входе планарный граф, в котором все внутренние грани являются треугольниками и все внешние вершины помечены положительными числами. Алгоритм даёт упаковку кругов, точки касания которых представляют заданный граф и для которого круги, представляющие внешние вершины, имеют заданный во входе радиус. Как они предположили, ключ к проблеме лежит в первоначальном вычислении радиусов кругов упаковки. Если радиусы известны, геометрические положения кругов нетрудно вычислить. Они начинают с пробных радиусов, которые не соответствуют реальным упаковкам, а потом в цикле выполняют следующие шаги:

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

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

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

История

Теорема об упаковке кругов впервые доказана Паулем КёбеШаблон:Sfn.

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

См. также

Примечания

Шаблон:Примечания

Литература

Ссылки

Шаблон:Rq

Шаблон:Задачи упаковки

  1. ↑ Если центры кругов образуют прямоугольную решётку, упаковка называется квадратной. Если же центры кругов образуют треугольную решётку, упаковка называется шестиугольной
Источник — https://ru.wiki.beta.math.wmflabs.org/w/index.php?title=Теорема_об_упаковке_кругов&oldid=16135