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

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

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

Для двумерного евклидова пространства Жозеф Луи Лагранж доказал в 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]. Роберт Лэнг использовал математику упаковки кругов для разработки компьютерных программ, предназначенных для разработки сложных фигур оригами.

• 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 Dec 2004). Дата обращения: 7 июня 2016.
• David de Laat, Fernando Mario de Oliveira Filho, Frank Vallentin. Upper bounds for packings of spheres of several radii (неопр.) (12 June 2012). Дата обращения: 7 июня 2016.