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

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

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

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

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

Упаковки на плоскости

Для двумерного евклидова пространства Жозеф Луи Лагранж доказал в 1773, что решётчатая упаковка кругов высшей плотности — это шестиугольная упаковка, в которой центры кругов располагаются на шестиугольной решётке (расположенные зигзагом ряды, подобные сотам), а каждый круг окружён шестью другими окружностями. Плотность такой упаковки равна

<math>\eta_h = \frac{\pi}{2\sqrt{3}} \approx 0.9069.</math>

Аксель Туэ привёл первое доказательство, что эта упаковка оптимальна в 1890, показав,что шестиугольная решётка является самой плотной из всех возможных упаковок кругов, как регулярных, так и нерегулярных. Однако это доказательство считалось не вполне полным. Первое полноценное доказательство приписывается Ласло Фейеш Тоту (1940) .

С другой стороны, были обнаружены жёсткие упаковки кругов низкой плотности.

Однородные упаковки

Существует 11 упаковок кругов на основе 11 однородных мозаик плоскости. В этих упаковках любая окружность может быть отображена на любую другую окружность путём отражения или вращения. Шестиугольные промежутки могут быть заполнены одним кругом, а двенадцатиугольные промежутки могут быть заполнены 7 кругами, образуя 3-однородные упаковки. Усечённая тришестиугольная мозаика с обоими типами промежутков могут быть заполнена как 4-однородная упаковка. Плосконосая шестиугольная мозаика имеет две зеркальные формы.

1-однородные упаковки, основанные на однородных мозаиках

Треугольная	Квадратная	Шестиугольная	Удлинённая треугольная
Тришестиугольная	Плосконосая квадратная	Усечённая квадратная	Усечённая шестиугольная
Ромботришестиугольная	Плосконосая шестиугольная	Плосконосая шестиугольная (зеркальная)	Усечённая тришестиугольная

Упаковка на сфере

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

Упаковка в ограниченных областях

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

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

Существует также ряд задач, которые разрешают размеры кругов быть неоднородными. Одним из таких расширений является задача нахождения максимально возможной плотности системы с двумя размерами кругов (бинарная система). Только девять определённых отношений радиусов позволяют компактную упаковку, в которой, если две окружности касаются, они вместе касаются также ещё двух кругов (если соединить отрезками центры касающихся окружностей, они триангулируют поверхность). Для семи таких отношений радиусов известны компактные упаковки, на которых достигается максимальное возможное отношение упаковки (выше, чем для кругов одного диаметра) для смеси кругов данного отношения радиусов. Высшая плотность упаковки — 0.911627478 для отношения радиусов 0.545151042•.

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

Приложения упаковки кругов

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

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

См. также

• Сетка Аполлония
• Упаковка кругов в квадрате
• Упаковка кругов в круге
• Инвертируемое расстояние
• Гипотеза Кеплера
• Окружности Мальфатти
• Задачи упаковки

Литература

• 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.
• [arxiv.org/abs/math/0412418 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. [arxiv.org/abs/1206.2608 Upper bounds for packings of spheres of several radii] (12 June 2012). Проверено 7 июня 2016.

Отрывок, характеризующий Упаковка кругов

– И весь свет узнал…
Тем анекдот и кончился. Хотя и непонятно было, для чего он его рассказывает и для чего его надо было рассказать непременно по русски, однако Анна Павловна и другие оценили светскую любезность князя Ипполита, так приятно закончившего неприятную и нелюбезную выходку мсье Пьера. Разговор после анекдота рассыпался на мелкие, незначительные толки о будущем и прошедшем бале, спектакле, о том, когда и где кто увидится.


Поблагодарив Анну Павловну за ее charmante soiree, [очаровательный вечер,] гости стали расходиться.
Пьер был неуклюж. Толстый, выше обыкновенного роста, широкий, с огромными красными руками, он, как говорится, не умел войти в салон и еще менее умел из него выйти, то есть перед выходом сказать что нибудь особенно приятное. Кроме того, он был рассеян. Вставая, он вместо своей шляпы захватил трехугольную шляпу с генеральским плюмажем и держал ее, дергая султан, до тех пор, пока генерал не попросил возвратить ее. Но вся его рассеянность и неуменье войти в салон и говорить в нем выкупались выражением добродушия, простоты и скромности. Анна Павловна повернулась к нему и, с христианскою кротостью выражая прощение за его выходку, кивнула ему и сказала:
– Надеюсь увидать вас еще, но надеюсь тоже, что вы перемените свои мнения, мой милый мсье Пьер, – сказала она.
Когда она сказала ему это, он ничего не ответил, только наклонился и показал всем еще раз свою улыбку, которая ничего не говорила, разве только вот что: «Мнения мнениями, а вы видите, какой я добрый и славный малый». И все, и Анна Павловна невольно почувствовали это.
Князь Андрей вышел в переднюю и, подставив плечи лакею, накидывавшему ему плащ, равнодушно прислушивался к болтовне своей жены с князем Ипполитом, вышедшим тоже в переднюю. Князь Ипполит стоял возле хорошенькой беременной княгини и упорно смотрел прямо на нее в лорнет.
– Идите, Annette, вы простудитесь, – говорила маленькая княгиня, прощаясь с Анной Павловной. – C'est arrete, [Решено,] – прибавила она тихо.
Анна Павловна уже успела переговорить с Лизой о сватовстве, которое она затевала между Анатолем и золовкой маленькой княгини.
– Я надеюсь на вас, милый друг, – сказала Анна Павловна тоже тихо, – вы напишете к ней и скажете мне, comment le pere envisagera la chose. Au revoir, [Как отец посмотрит на дело. До свидания,] – и она ушла из передней.
Князь Ипполит подошел к маленькой княгине и, близко наклоняя к ней свое лицо, стал полушопотом что то говорить ей.
Два лакея, один княгинин, другой его, дожидаясь, когда они кончат говорить, стояли с шалью и рединготом и слушали их, непонятный им, французский говор с такими лицами, как будто они понимали, что говорится, но не хотели показывать этого. Княгиня, как всегда, говорила улыбаясь и слушала смеясь.
– Я очень рад, что не поехал к посланнику, – говорил князь Ипполит: – скука… Прекрасный вечер, не правда ли, прекрасный?
– Говорят, что бал будет очень хорош, – отвечала княгиня, вздергивая с усиками губку. – Все красивые женщины общества будут там.
– Не все, потому что вас там не будет; не все, – сказал князь Ипполит, радостно смеясь, и, схватив шаль у лакея, даже толкнул его и стал надевать ее на княгиню.
От неловкости или умышленно (никто бы не мог разобрать этого) он долго не опускал рук, когда шаль уже была надета, и как будто обнимал молодую женщину.
Она грациозно, но всё улыбаясь, отстранилась, повернулась и взглянула на мужа. У князя Андрея глаза были закрыты: так он казался усталым и сонным.
– Вы готовы? – спросил он жену, обходя ее взглядом.
Князь Ипполит торопливо надел свой редингот, который у него, по новому, был длиннее пяток, и, путаясь в нем, побежал на крыльцо за княгиней, которую лакей подсаживал в карету.
– Рrincesse, au revoir, [Княгиня, до свиданья,] – кричал он, путаясь языком так же, как и ногами.
Княгиня, подбирая платье, садилась в темноте кареты; муж ее оправлял саблю; князь Ипполит, под предлогом прислуживания, мешал всем.
– Па звольте, сударь, – сухо неприятно обратился князь Андрей по русски к князю Ипполиту, мешавшему ему пройти.
– Я тебя жду, Пьер, – ласково и нежно проговорил тот же голос князя Андрея.
Форейтор тронулся, и карета загремела колесами. Князь Ипполит смеялся отрывисто, стоя на крыльце и дожидаясь виконта, которого он обещал довезти до дому.

– Eh bien, mon cher, votre petite princesse est tres bien, tres bien, – сказал виконт, усевшись в карету с Ипполитом. – Mais tres bien. – Он поцеловал кончики своих пальцев. – Et tout a fait francaise. [Ну, мой дорогой, ваша маленькая княгиня очень мила! Очень мила и совершенная француженка.]
Ипполит, фыркнув, засмеялся.
– Et savez vous que vous etes terrible avec votre petit air innocent, – продолжал виконт. – Je plains le pauvre Mariei, ce petit officier, qui se donne des airs de prince regnant.. [А знаете ли, вы ужасный человек, несмотря на ваш невинный вид. Мне жаль бедного мужа, этого офицерика, который корчит из себя владетельную особу.]
Ипполит фыркнул еще и сквозь смех проговорил:
– Et vous disiez, que les dames russes ne valaient pas les dames francaises. Il faut savoir s'y prendre. [А вы говорили, что русские дамы хуже французских. Надо уметь взяться.]
Пьер, приехав вперед, как домашний человек, прошел в кабинет князя Андрея и тотчас же, по привычке, лег на диван, взял первую попавшуюся с полки книгу (это были Записки Цезаря) и принялся, облокотившись, читать ее из середины.
– Что ты сделал с m lle Шерер? Она теперь совсем заболеет, – сказал, входя в кабинет, князь Андрей и потирая маленькие, белые ручки.
Пьер поворотился всем телом, так что диван заскрипел, обернул оживленное лицо к князю Андрею, улыбнулся и махнул рукой.
– Нет, этот аббат очень интересен, но только не так понимает дело… По моему, вечный мир возможен, но я не умею, как это сказать… Но только не политическим равновесием…
Князь Андрей не интересовался, видимо, этими отвлеченными разговорами.
– Нельзя, mon cher, [мой милый,] везде всё говорить, что только думаешь. Ну, что ж, ты решился, наконец, на что нибудь? Кавалергард ты будешь или дипломат? – спросил князь Андрей после минутного молчания.
Пьер сел на диван, поджав под себя ноги.
– Можете себе представить, я всё еще не знаю. Ни то, ни другое мне не нравится.
– Но ведь надо на что нибудь решиться? Отец твой ждет.
Пьер с десятилетнего возраста был послан с гувернером аббатом за границу, где он пробыл до двадцатилетнего возраста. Когда он вернулся в Москву, отец отпустил аббата и сказал молодому человеку: «Теперь ты поезжай в Петербург, осмотрись и выбирай. Я на всё согласен. Вот тебе письмо к князю Василью, и вот тебе деньги. Пиши обо всем, я тебе во всем помога». Пьер уже три месяца выбирал карьеру и ничего не делал. Про этот выбор и говорил ему князь Андрей. Пьер потер себе лоб.
– Но он масон должен быть, – сказал он, разумея аббата, которого он видел на вечере.
– Всё это бредни, – остановил его опять князь Андрей, – поговорим лучше о деле. Был ты в конной гвардии?…
– Нет, не был, но вот что мне пришло в голову, и я хотел вам сказать. Теперь война против Наполеона. Ежели б это была война за свободу, я бы понял, я бы первый поступил в военную службу; но помогать Англии и Австрии против величайшего человека в мире… это нехорошо…
Князь Андрей только пожал плечами на детские речи Пьера. Он сделал вид, что на такие глупости нельзя отвечать; но действительно на этот наивный вопрос трудно было ответить что нибудь другое, чем то, что ответил князь Андрей.
– Ежели бы все воевали только по своим убеждениям, войны бы не было, – сказал он.
– Это то и было бы прекрасно, – сказал Пьер.
Князь Андрей усмехнулся.
– Очень может быть, что это было бы прекрасно, но этого никогда не будет…
– Ну, для чего вы идете на войну? – спросил Пьер.
– Для чего? я не знаю. Так надо. Кроме того я иду… – Oн остановился. – Я иду потому, что эта жизнь, которую я веду здесь, эта жизнь – не по мне!


В соседней комнате зашумело женское платье. Как будто очнувшись, князь Андрей встряхнулся, и лицо его приняло то же выражение, какое оно имело в гостиной Анны Павловны. Пьер спустил ноги с дивана. Вошла княгиня. Она была уже в другом, домашнем, но столь же элегантном и свежем платье. Князь Андрей встал, учтиво подвигая ей кресло.
– Отчего, я часто думаю, – заговорила она, как всегда, по французски, поспешно и хлопотливо усаживаясь в кресло, – отчего Анет не вышла замуж? Как вы все глупы, messurs, что на ней не женились. Вы меня извините, но вы ничего не понимаете в женщинах толку. Какой вы спорщик, мсье Пьер.
– Я и с мужем вашим всё спорю; не понимаю, зачем он хочет итти на войну, – сказал Пьер, без всякого стеснения (столь обыкновенного в отношениях молодого мужчины к молодой женщине) обращаясь к княгине.
Княгиня встрепенулась. Видимо, слова Пьера затронули ее за живое.
– Ах, вот я то же говорю! – сказала она. – Я не понимаю, решительно не понимаю, отчего мужчины не могут жить без войны? Отчего мы, женщины, ничего не хотим, ничего нам не нужно? Ну, вот вы будьте судьею. Я ему всё говорю: здесь он адъютант у дяди, самое блестящее положение. Все его так знают, так ценят. На днях у Апраксиных я слышала, как одна дама спрашивает: «c'est ca le fameux prince Andre?» Ma parole d'honneur! [Это знаменитый князь Андрей? Честное слово!] – Она засмеялась. – Он так везде принят. Он очень легко может быть и флигель адъютантом. Вы знаете, государь очень милостиво говорил с ним. Мы с Анет говорили, это очень легко было бы устроить. Как вы думаете?