WikiSort.ru - Не сортированное

Шестиугольная упаковка кругов

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

Аналоги круга в других размерностях не могут быть упакованы с абсолютной эффективностью в размерностях, больших единицы (в одномерном пространстве аналог окружности — просто две точки). Таким образом, всегда останется незанятое пространство при упаковке исключительно кругами. Наиболее эффективный путь упаковки кругов, шестиугольная упаковка, даёт примерно 91 % эффективности^[7].

Упаковка сфер в высших размерностях

В трёхмерном пространстве гранецентрированная решётка даёт оптимальную упаковку сфер. Доказано, что 8-мерная решётка E8 и 24-мерная решётка Лича оптимальны в соответствующих пространствах.

Упаковка платоновых тел в трёхмерных пространствах

Кубы легко могут быть расположены в трёхмерном пространстве так, что они полностью заполнят пространство. Наиболее естественная упаковка — кубические соты^[en]*. Никакой другой правильный многогранник не может заполнить полностью пространство, но некоторые результаты известны. Тетраэдр^[en] может дать упаковку по меньшей мере 85 %. Одна из лучших упаковок правильными додекаэдрами основывается на вышеупомянутой гранецентрированной кубической решётке.

Тетраэдры и октаэдры вместе могут заполнить всё пространство в конфигурации, известной как тетраэдрально-октаэдральная мозаика^[en].

Тело	Оптимальная плотность решётчатой упаковки
икосаэдры	0.836357…[8]
додекаэдры	${\displaystyle (5+{\sqrt {5}})/8=0.904508...}$ [8]
октаэдры	18/19 = 0.947368…[9]

Моделирование, совмещающее методы локального улучшения со случайно сгенерированными упаковками, наводит на мысль, что решётчатые упаковки для икосаэдра, додекаэдра и октаэдра являются оптимальными и в более широком классе всех упаковок^[3].

Сферы в евклидов шар

Задача нахождения наименьшего шара, в который можно упаковать без перекрытия ${\displaystyle k}$ открытых единичных шаров, имеет простой и полный ответ в ${\displaystyle n}$ -мерном евклидовом пространстве, если ${\displaystyle \scriptstyle k\leq n+1}$ , а в бесконечномерном гильбертовом пространстве — без ограничений. Имеет смысл описать его здесь с целью показать общую проблему. В этом случае возможна конфигурация ${\displaystyle k}$ попарно касающихся единичных шаров. Разместим центры в вершинах ${\displaystyle a_{1},..,a_{k}}$ правильного ${\displaystyle \scriptstyle (k-1)}$ мерного симплекса с ребром 2. Это легко сделать, начав с ортонормированного базиса. Лёгкие вычисления показывают, что расстояние от любой вершины до центра тяжести равно ${\displaystyle \scriptstyle {\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ . Кроме того, любая другая точка пространства имеет большее расстояние по меньшей мере до одной из ${\displaystyle \scriptstyle k}$ вершин. В терминах включения шаров, ${\displaystyle \scriptstyle k}$ открытых единичных шаров, имеющих центры в точках ${\displaystyle \scriptstyle a_{1},..,a_{k}}$ , попадают в шар радиуса ${\displaystyle \scriptstyle r_{k}:=1+{\sqrt {2{\big (}1-{\frac {1}{k}}{\big )}}}}$ , который минимален для такой конфигурации.

Чтобы показать, что такая конфигурация оптимальна, допустим, что ${\displaystyle \scriptstyle x_{1},...,x_{k}}$  — центры ${\displaystyle \scriptstyle k}$ непересекающихся открытых единичных шаров, находящихся в шаре с радиусом ${\displaystyle \scriptstyle r}$ и центром в точке ${\displaystyle \scriptstyle x_{0}}$ . Рассмотрим отображение из конечного множества ${\displaystyle \scriptstyle \{x_{1},..x_{k}\}}$ в ${\displaystyle \scriptstyle \{a_{1},..a_{k}\}}$ , сопоставляющее ${\displaystyle \scriptstyle x_{j}}$ в ${\displaystyle \scriptstyle a_{j}}$ для всех ${\displaystyle \scriptstyle 1\leq j\leq k}$ . Поскольку для всех ${\displaystyle \scriptstyle 1\leq i<j\leq k}$ , ${\displaystyle \scriptstyle \|a_{i}-a_{j}\|=2\leq \|x_{i}-x_{j}\|}$ , это отображение 1-липшицево и по теореме Киршбрауна оно распространяется до глобально определённого 1-липшицева отображения. В частности, существует точка ${\displaystyle \scriptstyle a_{0}}$ , такая что для всех ${\displaystyle \scriptstyle 1\leq j\leq k}$ имеем ${\displaystyle \scriptstyle \|a_{0}-a_{j}\|\leq \|x_{0}-x_{j}\|}$ , а следовательно, ${\displaystyle \scriptstyle r_{k}\leq 1+\|a_{0}-a_{j}\|\leq 1+\|x_{0}-x_{j}\|\leq r}$ . Это показывает, что существуют ${\displaystyle \scriptstyle k}$ непересекающихся единичных открытых шаров в шаре радиусом ${\displaystyle \scriptstyle r}$ тогда и только тогда, когда ${\displaystyle \scriptstyle r\geq r_{k}}$ . Заметим, что в случае бесконечномерного гильбертова пространства отсюда следует существование бесконечного числа непересекающихся единичных открытых шаров внутри шара радиуса ${\displaystyle \scriptstyle r}$ тогда и только тогда, когда ${\displaystyle \scriptstyle r\geq 1+{\sqrt {2}}}$ . Например, единичные шары с центрами в ${\displaystyle \scriptstyle {\sqrt {2}}e_{j}}$ , где ${\displaystyle \scriptstyle \{e_{j}\}_{j}}$  — ортонормальный базис, не пересекаются и содержатся в шаре радиуса ${\displaystyle \scriptstyle 1+{\sqrt {2}}}$ с центром в начале координат. Более того, для ${\displaystyle \scriptstyle r<1+{\sqrt {2}}}$ максимальное число непересекающихся открытых единичных шаров внутри шара радиуса r равно ${\displaystyle \scriptstyle {\big \lfloor }{\frac {2}{2-(r-1)^{2}}}{\big \rfloor }}$ .

Сферы в параллелепипед

Задача определяет число сферических объектов заданного диаметра d, которые могут быть упакованы в прямоугольный параллелепипед размера a × b × c.

Одинаковые сферы в цилиндр

Задача определяет минимальную высоту h цилиндра с заданным радиусом R, в который упаковано n одинаковых шаров радиуса r (< R) ^[10].

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

Круги в круге

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

Упаковка n единичных кругов в как можно меньшую окружность. Задача тесно связана с распределением точек в единичной окружности с целью достичь наибольшего минимального расстояния d_n между точками.

Оптимальные решения были доказаны для n≤13 и для n=19.

Круги в квадрате

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

Упаковка n единичных кругов в как можно меньший квадрат. Задача тесно связана с распределением точек в единичном квадрате с целью достичь наибольшего минимального расстояния d_n между точками^[11]. Для преобразования двух этих формулировок задачи размер квадрата единичных кругов будет L=2+2/d_n.

Оптимальные решения были доказаны для n≤30^[12].

Круги в равнобедренном прямоугольном треугольнике

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

Упаковка n единичных кругов в как можно меньший равнобедренный прямоугольный треугольник^[en]. Хорошие приближения известны для n<300 ^[13].

Круги в правильном треугольнике

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

Упаковка n единичных кругов в как можно меньший правильный треугольник. Оптимальные решения известны для n<13, а для n<28 высказаны гипотезы^[14].

Упаковка квадратов

Квадраты в квадрате

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

Упаковка n единичных квадратов в как можно меньший квадрат.

Оптимальные решения доказаны для n=1-10, 14-16, 23-25, 34-36, 62-64, 79-81, 98-100 и любого полного квадрата ^[15].

Незаполненное пространство асимптотически равно O(a^7/11) ^[16].

Упаковка прямоугольников