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

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

Наиболее эффективный способ упаковать круги различных размеров не очевиден

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

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

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

Упаковки на плоскости

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

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

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

${\displaystyle \eta _{h}={\frac {\pi }{2{\sqrt {3}}}}\approx 0.9069.}$

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

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

Однородные упаковки

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

1-однородные упаковки, основанные на однородных мозаиках

Треугольная	Квадратная	Шестиугольная	Удлинённая треугольная^[англ.]
Тришестиугольная	Плосконосая квадратная	Усечённая квадратная	Усечённая шестиугольная^[англ.]
Ромботришестиугольная^[англ.]	Плосконосая шестиугольная	Плосконосая шестиугольная (зеркальная)	Усечённая тришестиугольная^[англ.]

Упаковка на сфере

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

Упаковка в ограниченных областях

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

Основная статья: Упаковка кругов в круге

Основная статья: Упаковка кругов в квадрате

Основная статья: Упаковка кругов в правильном треугольнике

Основная статья: Упаковка кругов в равнобедренном прямоугольном треугольнике

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

Неравные круги

Компактная упаковка бинарных кругов с наиболее близкими размерами кругов^[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. Chang, Hai-Chau; Wang, Lih-Chung (2010). "A Simple Proof of Thue's Theorem on Circle Packing". arXiv:1009.4322 [math.MG].
3. Williams, 1979, с. 35-39.
4. Kennedy, 2006, с. 255–267.
5. Heppes, 2003, с. 241–262.
6. Kennedy.
7. de Laat, de Oliveira Filho, Vallentin.
8. Лекции по современному оригами "Robert Lang on TED Архивная копия от 15 октября 2011 на Wayback Machine."

Литература

• Wells D. The Penguin Dictionary of Curious and Interesting Geometry. — New York: Penguin Books, 1991. — С. 30-31, 167. — ISBN 0-14-011813-6.
• Tom Kennedy. Compact packings of the plane with two sizes of discs // Discrete and Computational Geometry. — 2006. — Т. 35. — С. 255–267. — doi:10.1007/s00454-005-1172-4. — arXiv:math/0407145v2.
• Aladár Heppes. Some Densest Two-Size Disc Packings in the Plane. — 2003. — Т. 30, вып. 2. — С. 241–262. — doi:10.1007/s00454-003-0007-6.
• Robert Williams. The Geometrical Foundation of Natural Structure: A Source Book of Design. — Dover Publications, Inc., 1979. — ISBN 0-486-23729-X.
• Kenneth Stephenson. Circle Packing: A Mathematical Tale // Notices of the American Mathematical Society. — 2003. — Т. 50, вып. 11.
• Tom Kennedy. A densest compact planar packing with two sizes of discs  (неопр.) (21 декабря 2004). Дата обращения: 7 июня 2016.
• David de Laat, Fernando Mario de Oliveira Filho, Frank Vallentin. Upper bounds for packings of spheres of several radii  (неопр.) (12 июня 2012). Дата обращения: 7 июня 2016.