Русский
Русский
English
Статистика
Реклама

Упаковка окружностей

Перевод Математика социальной дистанции это урок геометрии

22.07.2020 14:19:29 | Автор: admin

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




Может показаться, что такая темя, как упаковка сфер придётся по душе только математикам. Кому ещё будет интересно искать наиболее эффективные способы размещения окружностей на плоскости или сфер в пространстве?

Однако сегодня миллионы людей по всему миру размышляют именно об этой задаче.

Определить, как безопасно открыть здания и общественные места, соблюдая социальную дистанцию это, в частности, упражнение в геометрии. Если каждый человек должен находиться на расстоянии не менее полутора метров от других людей, тогда чтобы посчитать, сколько человек может сидеть в классе или столовой, нужно упаковать непересекающиеся окружности на плане помещения.



Естественно, для борьбы с коронавирусом нужно решить гораздо больше задач, чем эта, геометрическая. Однако упаковка окружностей и сфер играет в этом свою роль так же, как моделирование кристаллических структур в химии и абстрактные пространства сообщений в теории информации. Эта задача, кажущаяся простой по описанию, занимала умы величайших математиков в истории, и интереснейшие исследования в этой области ведутся и сегодня, в частности, в высших измерениях. К примеру, недавно математики нашли наилучший способ упаковки в 8- и 24-мерных пространствах а эта техника необходима для оптимизации кодов коррекции ошибок, используемых как в сотовых телефонах, так и в обмене информацией с космическими зондами. Так что давайте посмотрим на некоторые из неожиданных сложностей, возникающих, когда мы пытаемся заполнить пространство простейшей из форм.

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

Вот один из примеров упаковки окружностей на плоскости. Похоже на вид сверху на упаковку газировки:



Можно представить, как эта закономерность повторяется по всем направлениям, как плитка, которой замостили плоскость. Небольшие промежутки между окружностями говорят о том, что плоскость заполнена не полностью, однако в случае с упаковкой окружностей этого следует ожидать. Нам же интересно, какой процент плоскости оказывается покрытым. Это будет плотность упаковки конкретного метода.

Приведённый выше метод называется квадратной упаковкой, и не зря центры окружностей можно представить в роли вершин квадратов.



И на самом деле, эти квадраты сами замощают плоскость:



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



Допустим, радиус окружности равен r. Это означает, что длина стороны квадрата равна 2r. В каждой из вершин квадрата находится четверть круга, поэтому процент покрытия каждого квадрата просто равен отношению площади одного полного круга к площади одного полного квадрата:

$ \frac{\pi r^2}{(2r)^2} = \frac{\pi r^2}{4r^2} = \frac{\pi }{4} \approx 0,7854 $



Каждый квадрат примерно на 78,54% покрыт окружностями, поэтому, учитывая замощение плоскости, вся она покрыта окружностями примерно на 78,54%. Такова плотность квадратной упаковки. Заметьте, что из ответа исчез радиус r. И в этом есть смысл: неважно, какого размера окружности, в квадрате всё равно будет четыре четверти круга.

Если вы пытались складывать банки с газировкой на боку следующим образом, а они соскальзывали и заполняли промежутки, вы знаете, что существует ещё один способ упаковать окружности на плоскости:



Применим сходный с предыдущим подход, и представим, что центры окружностей в данном случае формируют правильные шестиугольники.



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

image

Какая часть шестиугольника покрыта кругами? Поскольку у правильного шестиугольника внутренний угол равен 120, в каждом из углов находится по трети круга. Получается два полных круга, а средний круг идёт третьим. Поэтому каждый шестиугольник покрывается тремя кругами. Если радиус каждого круга r, получается площадь в 3r.

image

Как это соотносится с площадью шестиугольника? Шестиугольник с длиной стороны s это шесть равносторонних треугольников с длиной стороны s, площадь каждого из которых равна s23/4. Поэтому площадь шестиугольника равна 6 * s23/4 = 6 s23/4. Поскольку длина стороны нашего шестиугольника равна 2r, его площадь равна:

$ \frac{6 s^2 \sqrt3}{4} = \frac{6 (2r)^2 \sqrt3}{4} = \frac{24 r^2 \sqrt3}{4} = 6 r^2 \sqrt3 $



Теперь можно вычислить процент покрытой кругами площади шестиугольника (поделив площадь шести кругов на площадь шестиугольника):

$ \frac{3 \pi r^2}{6 r^2 \sqrt3} = \frac{3 \pi}{6 \sqrt3} = \frac{\pi}{2 \sqrt3} \approx 0,9069 $



Каждый шестиугольник примерно на 90,69% покрыт кругами, поэтому такая упаковка будет куда как более эффективной, чем квадратная. Заметьте, как радиус круга снова исчез, как и ожидалось. На самом деле, более эффективной упаковки не существует.

Но доказать это было нелегко. Такие знаменитые математики, как Жозеф Луи Лагранж и Карл Фридрих Гаусс начали работать над этим в конце XVIII и начале XIX веков, однако полностью проблему решили только в 1940-х, тщательно обработав все возможные расположения периодические и непериодические. То, что на решение задачи в двух измерениях, где всё достаточно легко представить, ушло так много времени, может служить предупреждением тому, что ждёт нас в высших измерениях.

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



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



Для шестиугольной упаковки мы размещали новые слои в промежутках предыдущего.



Разные упаковки получаются в зависимости от того, как мы соединяем копии разных слоёв.

В трёх измерениях от такого размещения слоёв друг на друге возникают фундаментально разные упаковки.



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



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



Разместить третий слой можно двумя способами. Можно выровнять промежутки с нижними, и оставить каналы открытыми. Вот вид сбоку на такое расположение:



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



Другой вариант размещения третьего слоя закрытие каналов. Сферы в третьем слое помещаются прямо над промежутками первого:



Это называется гранецентрированной кубической (ГК) или кубической плотной упаковкой. Если посмотреть сверху, промежутков не будет.



Два этих схожих, но фундаментально разных расположения, возникают в химии, описывая расположение атомов в разных материалах. К примеру, у таких металлов, как серебро и золото структура имеет вид ГК, а у металлов типа цинка и титана ШПУ. Каждый метод из двух позволяет заполнить пространство сферами. В методе ШПУ в каждом втором слое сферы расположены абсолютно одинаково, а в ГК в каждом третьем. Можно создавать бесконечное количество разных упаковок, комбинируя оба этих метода, однако интересно, что и ШПУ, и ГК дают оптимальную упаковку! Их плотность упаковки не только одинаковая, 32 0,7405 это наиболее плотная из возможных упаковок в трёхмерном пространстве. Знаменитый математик и астроном Иоганн Кеплер предположил это в 1611 году, однако полное доказательство смог вывести только математик Томас Хейлс в 1998 году.



В трёхмерном пространстве есть больше места, и у нас есть больше способов эффективно упаковать сферы. При добавлении размерностей сложность упаковки только возрастает там больше места, больше возможностей, а представить это себе тяжелее. Кроме того, в высших измерениях сферы становятся меньше!



Рассмотрим окружность, вписанную в квадрат с длиной стороны 1.

Радиус окружности r = 1/2, поэтому отношение площади круга к площади квадрата равно:

$ \frac{\pi r^2}{s^2} = \frac{\pi (\frac{1}{2})^2}{1^2} = \frac{\pi }{4} \approx 0,7854 $



Что также равно плотности упаковки квадрата в двух измерениях.

Теперь рассмотрим объём сферы, вписанной в единичный куб.



Радиус сферы опять равен r = 1/2, поэтому отношение объёма сферы к объёму куба равно:

$ \frac{\frac{4}{3}\pi r^3}{s^3} = \frac{\frac{4}{3}\pi (\frac{1}{2})^3}{1^3} = \frac{4}{3}\pi (\frac{1}{8}) = \frac{\pi}{6} \approx 0,5236 $



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

Это можно показать при помощи алгебры, но можно и понять, если задуматься об углах. В любом измерении можно вписать n-мерную сферу в n-мерный куб. Сфера касается граней куба, но не доходит до углов, поэтому вокруг каждого угла есть регион, находящийся внутри куба, но снаружи сферы. Однако у n-мерной коробки будет 2 n углов, то есть, с увеличением n количество непокрытых сферой участков растёт экспоненциально. Кроме того, расстояние между углами и сферой также растёт. Это означает, что в долгосрочной перспективе пространство, находящееся внутри n-мерного куба, но снаружи n-мерной сферы просто задавит пространство, занимаемое сферой.

Если сжатие сфер вам кажется недостаточно странным, то математики, занимавшиеся упаковкой сфер, заметили нечто ещё более неожиданное в измерениях 8 и 24. В этих измерениях сферы уменьшаются как раз настолько, чтобы суметь заполнить промежутки между новыми сферами, что даёт сверхплотную упаковку в этих измерениях. Была высказана гипотеза об оптимальности этих особых методов, однако точно это не было известно до 2016 года, когда Марина Вязовская доказала эту теорему для 8-мерного пространства. Через неделю Вязовская с помощниками расширили её метод для доказательства и в случае 24-мерного пространства.

Из работы Вязовской следует, что теперь мы знаем наиболее эффективные способы упаковки сфер в измерениях 1, 2, 3, 8 и 24. Но в других измерениях остаётся ещё очень много работы. Так что доставайте апельсины и банки с газировкой, и начинайте экспериментировать. Возможно, именно вы сможете заполнить важные пробелы.

Упражнения


1. Допустим, мы начали упаковывать координатную плоскость так, как показано на рисунки ниже. Центр левого нижнего круга расположен в точке (0, 0), а центр правого нижнего круга в точке (2, 0).



В какой точке находится центр третьего круга?

2. Ниже начало простой кубической упаковки сфер. Какова плотность упаковки такой схемы?



3. Вот начало упаковки плоскости правильными восьмиугольниками.



Какова плотность такой упаковки?

Ответы


Задача 1
Центры кругов образуют равносторонний треугольник со стороной длины 2.



Благодаря симметрии, координата x центра третьего круга равна 1. Поскольку высота равностороннего треугольника со стороной s равна s3/2, то высота этого треугольника равна 23/2 = 3, что является координатой y центра третьего круга. Поэтому его центр расположен в точке (1, 3).


Задача 2
Как и в случае с квадратной упаковкой кругов на плоскости, плотность такой упаковки мы можем определить, изучив один куб.



В каждом из восьми углов куба располагается по одной восьмой части сферы. Поэтому внутри каждого куба помещается ровно по одной сфере. Если радиус каждой сферы r, то длина стороны куба 2r. В результате плотность упаковки равняется (объём сферы, делённый на объём куба):

$ \frac{\frac{4}{3}\pi r^3}{(2r)^3} = \frac{\frac{4}{3}\pi r^3}{8r^3} = \frac{\pi}{6} \approx 0,5236 $



Обратите внимание, что это отношение объёма сферы к объёму куба, которое мы нашли выше.



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



В квадрате находится ровно один восьмиугольник, разрезанный на четыре части. У правильного восьмиугольника со стороной длины s площадь равняется (2+22)s2 (что можно показать, различными образами разрезая восьмиугольник), кроме того, в середине квадрата остаётся непокрытым один квадратик со стороной s. Это даёт нам плотность упаковки (площадь восьмиугольника, делённая на сумму площади восьмиугольника и площади квадратика со стороной s):

$ \frac{(2 + 2\sqrt2) s^2}{(2 + 2\sqrt2) s^2 + s^2} = \frac{(2 + 2\sqrt2)}{(2 + 2\sqrt2) + 1} = \frac{2 + 2\sqrt2}{3 + 2\sqrt2} \approx 0,8284 $



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

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru