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

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

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

В то время как окружности имеют относительно низкую максимальную плотность упаковки 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-однородные упаковки. Усечённая тришестиугольная мозаика^[en] с обоими типами промежутков могут быть заполнена как 4-однородная упаковка. Плосконосая тришестиугольная мозаика имеет две зеркальные формы.

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Примечания

Литература

• 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.

Эта страница в последний раз была отредактирована 16 сентября 2023 в 11:02.