Упаковка кругов

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Статья описывает упаковку кругов на поверхностях. Для связанной статьи об упаковке кругов с заданным графом пересечений, см. статью «Теорема об упаковке кругов».
Наиболее эффективный способ упаковать круги различных размеров не очевиден

В геометрии упаковка кругов — это изучение размещения кругов (одного размера или разных размеров) на заданной поверхности таким образом, что они не пересекаются и круги касаются друг друга. Соответствующая плотность упаковки η размещения — это доля занятой кругами поверхности. Можно обобщить упаковки кругов на более высокие размерности — она называется упаковкой шаров, которая, обычно, работает с одинаковыми сферами.

В то время как окружности имеют относительно низкую максимальную плотность упаковки 0.9069 на евклидовой плоскости, эта плотность не минимальна. «Худшая» фигура упаковки плоскости не известна, хотя сглаженный восьмиугольник имеет плотность упаковки около 0.902414, что является наименьшей максимальной плотностью упаковки, известной для центрально-симметричных выпуклых фигур[1]. Плотность упаковки вогнутых фигур, таких как звёздчатые многоугольники, может быть произвольно малой.

Ветвь математики, известная как «упаковка кругов», занимается геометрией и комбинаторикой упаковок кругов произвольного размера и из неё подымаются дискретные аналоги конформных отображений, римановых поверхностей и им подобные.

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

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

Для двумерного евклидова пространства Жозеф Луи Лагранж доказал в 1773, что решётчатая упаковка кругов высшей плотности — это шестиугольная упаковка[2], в которой центры кругов располагаются на шестиугольной решётке (расположенные зигзагом ряды, подобные сотам), а каждый круг окружён шестью другими окружностями. Плотность такой упаковки равна

Аксель Туэ привёл первое доказательство, что эта упаковка оптимальна в 1890, показав,что шестиугольная решётка является самой плотной из всех возможных упаковок кругов, как регулярных, так и нерегулярных. Однако это доказательство считалось не вполне полным. Первое полноценное доказательство приписывается Ласло Фейеш Тоту (1940) [2].

С другой стороны, были обнаружены жёсткие упаковки кругов низкой плотности.

Однородные упаковки[править | править код]

Существует 11 упаковок кругов на основе 11 однородных мозаик плоскости[3]. В этих упаковках любая окружность может быть отображена на любую другую окружность путём отражения или вращения. Шестиугольные промежутки могут быть заполнены одним кругом, а двенадцатиугольные промежутки могут быть заполнены 7 кругами, образуя 3-однородные упаковки. Усечённая тришестиугольная мозаика[en] с обоими типами промежутков могут быть заполнена как 4-однородная упаковка. Плосконосая тришестиугольная мозаика имеет две зеркальные формы.

1-однородные упаковки, основанные на однородных мозаиках
Triangular tiling circle packing.png
Треугольная
Square tiling circle packing.png
Квадратная
Hexagonal tiling circle packing.png
Шестиугольная
Elongated triangular tiling circle packing.png
Удлинённая треугольная[en]
Trihexagonal tiling circle packing.png
Тришестиугольная
Snub square tiling circle packing.png
Плосконосая квадратная
Truncated square tiling circle packing.png
Усечённая квадратная
Truncated hexagonal tiling circle packing.png
Усечённая шестиугольная[en]
Rhombitrihexagonal tiling circle packing.png
Ромботришестиугольная[en]
Snub hexagonal tiling circle packing.png
Плосконосая шестиугольная
Snub hexagonal tiling mirror circle packing.png
Плосконосая шестиугольная (зеркальная)
Truncated rhombitrihexagonal tiling circle packing.png
Усечённая тришестиугольная[en]

Упаковка на сфере[править | править код]

Связанная задача — определение расположения с минимальной энергией одинаково расположенных точек, которые должны лежать на заданной поверхности. Задача Томсона[en] рассматривает распределение электрических зарядов с наименьшей энергией на поверхности сферы. Задача Таммеса[en] является обобщением этой задачи и максимизирует минимальное расстояние между кругами на сфере.

Упаковка в ограниченных областях[править | править код]

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

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

Неравные круги[править | править код]

Компактная упаковка бинарных кругов с наиболее близкими размерами кругов[4]. Упаковка также является самой плотной упаковкой кругов с этим отношением размеров (отношение 0.6375559772 с отношением упаковки (плотности) 0.910683)[5]

Существует также ряд задач, которые разрешают размеры кругов быть неоднородными. Одним из таких расширений является задача нахождения максимально возможной плотности системы с двумя размерами кругов (бинарная система). Только девять определённых отношений радиусов позволяют компактную упаковку, в которой, если две окружности касаются, они вместе касаются также ещё двух кругов (если соединить отрезками центры касающихся окружностей, они триангулируют поверхность)[4]. Для семи таких отношений радиусов известны компактные упаковки, на которых достигается максимальное возможное отношение упаковки (выше, чем для кругов одного диаметра) для смеси кругов данного отношения радиусов. Высшая плотность упаковки — 0.911627478 для отношения радиусов 0.545151042•[5][6].

Также известно, что если отношение радиусов выше 0.742, бинарная смесь не может быть упакована лучше, чем круги одного размера[5]. Верхние границы, которые могут быть достигнуты такой бинарной упаковкой для меньших отношений радиусов, также получены[7].

Приложения упаковки кругов[править | править код]

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

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

См. также[править | править код]

Примечания[править | править код]

  1. Weisstein, Eric W. Smoothed Octagon (англ.) на сайте Wolfram MathWorld.
  2. 1 2 Chang, Hai-Chau & Wang, Lih-Chung (2010), "A Simple Proof of Thue's Theorem on Circle Packing", arΧiv:1009.4322 [math.MG] 
  3. Williams, 1979, с. 35-39.
  4. 1 2 Kennedy, 2006, с. 255–267.
  5. 1 2 3 Heppes, 2003, с. 241–262.
  6. Kennedy.
  7. de Laat, de Oliveira Filho, Vallentin.
  8. Лекции по современному оригами "Robert Lang on TED."

Литература[править | править код]