В геометрии упаковка кругов — это изучение расположения кругов (равных или разных размеров) на заданной поверхности таким образом, что не происходит перекрытия и ни один круг не может быть увеличен без создания перекрытия. Соответствующая плотность упаковки , η , расположения — это доля поверхности , покрытая кругами. Обобщения могут быть сделаны на более высокие измерения — это называется упаковкой сфер , которая обычно имеет дело только с идентичными сферами.
Раздел математики, обычно известный как «упаковка кругов», занимается геометрией и комбинаторикой упаковок кругов произвольного размера: они приводят к дискретным аналогам конформных отображений , римановых поверхностей и т. п.
.svg/1280px-Circle_packing_(hexagonal).svg.png)
В двумерной евклидовой плоскости Жозеф Луи Лагранж доказал в 1773 году, что самая плотная решетчатая упаковка кругов — это гексагональная упаковка, [1] в которой центры кругов расположены в гексагональной решетке (шахматные ряды, как соты ) , а каждый круг окружен шестью другими кругами. Для кругов диаметром D и шестиугольников со стороной D площадь шестиугольника и площадь круга равны соответственно:
Площадь, покрытая кругами внутри каждого шестиугольника, составляет:
Наконец, плотность упаковки составляет:
В 1890 году Аксель Туэ опубликовал доказательство того, что эта же плотность является оптимальной среди всех упаковок, а не только решетчатых, но его доказательство некоторые посчитали неполным. Первое строгое доказательство приписывается Ласло Фейешу Тоту в 1942 году . [1] [2]
Хотя круг имеет относительно низкую максимальную плотность упаковки, он не имеет минимально возможной плотности даже среди центрально-симметричных выпуклых форм : сглаженный восьмиугольник имеет плотность упаковки около 0,902414, наименьшую известную для центрально-симметричных выпуклых форм и предположительно минимально возможную. [3] (Плотность упаковки вогнутых форм, таких как звездчатые многоугольники, может быть сколь угодно малой.)
С другой стороны, Бёрёцкий продемонстрировал, что существуют произвольно низкоплотные расположения жёстко упакованных кругов. [4] [5]
Существует одиннадцать упаковок кругов, основанных на одиннадцати однородных мозаиках плоскости. [6] В этих упаковках каждый круг может быть отображен на любой другой круг с помощью отражений и вращений. Шестиугольные промежутки могут быть заполнены одним кругом, а двенадцатиугольные промежутки могут быть заполнены семью кругами, создавая 3-однородные упаковки. Усеченная тришестиугольная мозаика с обоими типами промежутков может быть заполнена как 4-однородная упаковка. Плосконосая шестиугольная мозаика имеет две зеркальные формы.
Связанная задача — определить наименьшее энергетическое расположение одинаково взаимодействующих точек, которые ограничены тем, чтобы лежать в пределах заданной поверхности. Задача Томсона имеет дело с наименьшим распределением энергии идентичных электрических зарядов на поверхности сферы. Задача Таммеса является обобщением этой задачи, имея дело с максимизацией минимального расстояния между окружностями на сфере. Это аналогично распределению неточечных зарядов на сфере.
Упаковка кругов в простые ограниченные формы — распространенный тип задач в развлекательной математике . Влияние стенок контейнера важно, и гексагональная упаковка, как правило, не является оптимальной для небольшого количества кругов. Конкретные задачи этого типа, которые были изучены, включают:
Подробности смотрите в связанных статьях.
Существует также ряд проблем, которые допускают неравномерность размеров кругов. Одним из таких расширений является нахождение максимально возможной плотности системы с двумя определенными размерами кругов ( бинарной системы). Только девять конкретных соотношений радиусов допускают компактную упаковку , которая имеет место, когда каждая пара кругов в контакте находится во взаимном контакте с двумя другими кругами (когда отрезки линий проводятся от соприкасающегося центра круга к центру круга, они триангулируют поверхность). [7] Для всех этих соотношений радиусов известна компактная упаковка, которая достигает максимально возможной фракции упаковки (выше, чем у дисков одинакового размера) для смесей дисков с этим соотношением радиусов. [9] Все девять имеют упаковки, зависящие от соотношения, более плотные, чем равномерная гексагональная упаковка, как и некоторые соотношения радиусов без компактных упаковок. [10]
Также известно, что если отношение радиусов превышает 0,742, бинарная смесь не может быть упакована лучше, чем диски одинакового размера. [8] Также были получены верхние границы плотности, которые могут быть получены в таких бинарных упаковках при меньших отношениях. [11]
Квадратурная амплитудная модуляция основана на упаковке кругов в круги в фазово-амплитудном пространстве. Модем передает данные в виде ряда точек в двумерной фазово-амплитудной плоскости. Расстояние между точками определяет устойчивость передачи к шуму, а диаметр описывающей окружности определяет требуемую мощность передатчика. Производительность максимальна, когда созвездие кодовых точек находится в центрах эффективной упаковки кругов. На практике для упрощения декодирования часто используются неоптимальные прямоугольные упаковки.
Упаковка кругов стала важным инструментом в дизайне оригами , поскольку для каждой части оригами требуется круг бумаги. [12] Роберт Дж. Лэнг использовал математику упаковки кругов для разработки компьютерных программ, которые помогают в проектировании сложных фигур оригами.
![{\displaystyle {\begin{align}A_{\mathrm {H} }&={\frac {3{\sqrt {3}}}{2}}D^{2}\\[4pt]A_{\mathrm {C} }&={\frac {\pi }{4}}D^{2}\end{align}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/28cb2f36b873aa2e71ce641d35b0f85647bb2cf4)
![{\displaystyle {\begin{align}\eta ={\frac {A_{\mathrm {HC} }}{A_{\mathrm {H} }}}&={\frac {{\frac {3\pi }{4}}D^{2}}{{\frac {3{\sqrt {3}}}{2}}D^{2}}}\\[4pt]&={\frac {\pi }{2{\sqrt {3}}}}\approx 0.9069\end{align}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0ce7969e21bb1fa83cd9c7f81fa9eca8fa096e38)