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

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

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

Самая плотная упаковка

В двумерной евклидовой плоскости Жозеф Луи Лагранж доказал в 1773 году, что решетчатая упаковка кругов с наибольшей плотностью представляет собой гексагональную упаковку: ^[1] в которой центры кругов расположены в виде шестиугольной решетки (в шахматном порядке, наподобие сот ), а каждый круг окружен шестью другими кругами. Для кругов диаметром $D$ и шестиугольников с длиной стороны $D$ площадь шестиугольника и площадь круга равны соответственно:

{\begin{aligned}A_{\mathrm {H} }&={\frac {3{\sqrt {3}}}{2}}D^{2}\\[4pt]A_{\mathrm {C} }&={\frac {\pi }{4}}D^{2}\end{aligned}}

Площадь, покрытая кругами внутри каждого шестиугольника, равна:

A_{\mathrm {HC} }=3A_{\mathrm {C} }={\frac {3\pi }{4}}D^{2}

Наконец, плотность упаковки равна:

{\begin{aligned}\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{aligned}}

В 1890 году Аксель Туэ опубликовал доказательство того, что эта же плотность оптимальна для всех упаковок, а не только для решетчатых, но некоторые сочли его доказательство неполным. Первое строгое доказательство приписывается Ласло Фейешу Тоту в 1942 году. ^[1]^[2]

Хотя круг имеет относительно низкую максимальную плотность упаковки, она не имеет минимально возможной даже среди центрально-симметричных выпуклых форм : сглаженный восьмиугольник имеет плотность упаковки около 0,902414, наименьшую из известных для центрально-симметричных выпуклых форм и предположительно быть минимально возможным. ^[3] (Плотность упаковки вогнутых фигур, таких как звездчатые многоугольники, может быть сколь угодно малой.)

Другие упаковки

С другой стороны, Бёрочки продемонстрировал, что существуют жестко упакованные круги с произвольно низкой плотностью. ^[4]^[5]

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

На сфере

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

На ограниченных территориях

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

Подробности смотрите в связанных статьях.

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

Существует также ряд проблем, из-за которых размеры кругов могут быть неоднородными. Одним из таких расширений является поиск максимально возможной плотности системы с двумя конкретными размерами круга ( бинарной системы). Только девять конкретных соотношений радиусов допускают компактную упаковку , то есть когда каждая пара соприкасающихся кругов находится во взаимном контакте с двумя другими кругами (когда отрезки линий рисуются от соприкасающегося центра круга к центру круга, они образуют триангуляцию поверхности). ^[7] Для всех этих соотношений радиусов известна компактная насадка, которая обеспечивает максимально возможную долю упаковки (выше, чем у дисков одинакового размера) для смесей дисков с таким соотношением радиусов. ^[9] Все девять имеют упаковки с определенным соотношением, более плотные, чем однородная гексагональная упаковка, как и некоторые соотношения радиусов без компактных упаковок. ^[10]

Также известно, что если отношение радиусов превышает 0,742, бинарная смесь не может упаковываться лучше, чем диски одинакового размера. ^[8] Получены также верхние оценки плотности, которые можно получить в таких бинарных упаковках при меньших отношениях. ^[11]

Приложения

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

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

См. также

Ссылки

^ Jump up to: ^а ^б Чанг, Хай-Чау; Ван, Ли-Чунг (2010). «Простое доказательство теоремы Туэ об упаковке кругов». arXiv : 1009.4322 [ math.MG ].
^ Тот, Ласло Фейес (1942). «На самом тугом шарикоподшипнике». Математика . 48 :676-684. дои : 10.1007/BF01180035 . S2CID 123697077 .
^ Вайсштейн, Эрик В. «Сглаженный восьмиугольник» . Математический мир .
^ Борочки, К. (1964). «Über стабильная Kreis- und Kugelsysteme». Летопись Будапештского университета наук имени Роландо Этвёша, математический отдел . 7 : 79–82.
^ Кале, Мэтью (2012). «Разреженные локально заклинившие дисковые набивки». Анналы комбинаторики . 16 (4): 773–780. дои : 10.1007/s00026-012-0159-0 . S2CID 1559383 .
^ Уильямс, Роберт (1979). Геометрическая основа естественной структуры: справочник по дизайну . Dover Publications, Inc. с. 35-39. ISBN 0-486-23729-Х .
^ Jump up to: ^а ^б Том Кеннеди (2006). «Компактные упаковки самолета с дисками двух размеров». Дискретная и вычислительная геометрия . 35 (2): 255–267. arXiv : math/0407145 . дои : 10.1007/s00454-005-1172-4 . S2CID 11688453 .
^ Jump up to: ^а ^б Хеппес, Аладар (1 августа 2003 г.). «Некоторые самые плотные упаковки для дисков двух размеров в самолете» . Дискретная и вычислительная геометрия . 30 (2): 241–262. дои : 10.1007/s00454-003-0007-6 .
^ Бедарид, Николя; Ферник, Томас (2022). «Плотность бинарных дисковых упаковок: девять компактных упаковок». Дискретная и вычислительная геометрия . 67 (3): 787–810. arXiv : 2002.07168 . дои : 10.1007/s00454-021-00348-7 .
^ Кеннеди, Том (21 июля 2004 г.). «Круглые упаковки» . Проверено 11 октября 2018 г.
^ де Лаат, Дэвид; де Оливейра Фильо, Фернандо Марио; Валлентин, Франк (12 июня 2012 г.). «Верхние оценки для упаковок сфер нескольких радиусов». Форум математики, Сигма . 2 . arXiv : 1206.2608 . дои : 10.1017/fms.2014.24 . S2CID 11082628 .
^ Лекция TED.com о современном оригами « Роберт Лэнг на TED. Архивировано 15 октября 2011 г. в Wayback Machine ».

Библиография

Уэллс Д. (1991). Словарь любопытной и интересной геометрии Penguin . Нью-Йорк: Книги Пингвина. стр. 30–31, 167 . ISBN 0-14-011813-6 .
Стивенсон, Кеннет (декабрь 2003 г.). «Упаковка кругов: математическая сказка» (PDF) . Уведомления Американского математического общества . 50 (11).

[ChangWang-1] Jump up to: ^а ^б Чанг, Хай-Чау; Ван, Ли-Чунг (2010). «Простое доказательство теоремы Туэ об упаковке кругов». arXiv : 1009.4322 [ math.MG ].

[Toth-2] Тот, Ласло Фейес (1942). «На самом тугом шарикоподшипнике». Математика . 48 :676-684. дои : 10.1007/BF01180035 . S2CID 123697077 .

[3] Вайсштейн, Эрик В. «Сглаженный восьмиугольник» . Математический мир .

[4] Борочки, К. (1964). «Über стабильная Kreis- und Kugelsysteme». Летопись Будапештского университета наук имени Роландо Этвёша, математический отдел . 7 : 79–82.

[5] Кале, Мэтью (2012). «Разреженные локально заклинившие дисковые набивки». Анналы комбинаторики . 16 (4): 773–780. дои : 10.1007/s00026-012-0159-0 . S2CID 1559383 .

[6] Уильямс, Роберт (1979). Геометрическая основа естественной структуры: справочник по дизайну . Dover Publications, Inc. с. 35-39. ISBN 0-486-23729-Х .

[Kennedy-7] Jump up to: ^а ^б Том Кеннеди (2006). «Компактные упаковки самолета с дисками двух размеров». Дискретная и вычислительная геометрия . 35 (2): 255–267. arXiv : math/0407145 . дои : 10.1007/s00454-005-1172-4 . S2CID 11688453 .

[Heppes-8] Jump up to: ^а ^б Хеппес, Аладар (1 августа 2003 г.). «Некоторые самые плотные упаковки для дисков двух размеров в самолете» . Дискретная и вычислительная геометрия . 30 (2): 241–262. дои : 10.1007/s00454-003-0007-6 .

[bf-9] Бедарид, Николя; Ферник, Томас (2022). «Плотность бинарных дисковых упаковок: девять компактных упаковок». Дискретная и вычислительная геометрия . 67 (3): 787–810. arXiv : 2002.07168 . дои : 10.1007/s00454-021-00348-7 .

[Kennedy2-10] Кеннеди, Том (21 июля 2004 г.). «Круглые упаковки» . Проверено 11 октября 2018 г.

[11] де Лаат, Дэвид; де Оливейра Фильо, Фернандо Марио; Валлентин, Франк (12 июня 2012 г.). «Верхние оценки для упаковок сфер нескольких радиусов». Форум математики, Сигма . 2 . arXiv : 1206.2608 . дои : 10.1017/fms.2014.24 . S2CID 11082628 .

[12] Лекция TED.com о современном оригами « Роберт Лэнг на TED. Архивировано 15 октября 2011 г. в Wayback Machine ».

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

v т и Проблемы с упаковкой
Abstract packing	Bin Set
Circle packing	In a circle / equilateral triangle / isosceles right triangle / square Apollonian gasket Circle packing theorem Tammes problem (on sphere)
Sphere packing	Apollonian Finite In a sphere In a cube In a cylinder Close-packing Kissing number Sphere-packing (Hamming) bound
Other 2-D packing	Square packing
Other 3-D packing	Tetrahedron Ellipsoid
Puzzles	Conway Slothouber–Graatsma

Базы данных авторитетного контроля
International	FAST
National	France BnF data Israel United States
Other	IdRef