Просмотр кода страницы Упаковка кругов

:''Статья описывает упаковку кругов на поверхностях. Для связанной статьи об упаковке кругов с заданным  [[Граф пересечений|графом пересечений]], см. статью «[[Теорема об упаковке кругов]]».''
[[Файл:Citrus fruits.jpg|thumb|Наиболее эффективный способ упаковать круги различных размеров не очевиден]]

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

В то время как окружности имеют относительно низкую максимальную плотность упаковки 0.9069 на [[Двумерное пространство|евклидовой плоскости]], эта плотность не минимальна. «Худшая» фигура упаковки плоскости не известна, хотя [[сглаженный восьмиугольник]] имеет плотность упаковки около 0.902414, что является наименьшей максимальной плотностью упаковки, известной для центрально-симметричных выпуклых фигур<ref>{{MathWorld|urlname=SmoothedOctagon |title=Smoothed Octagon }}</ref>.
Плотность упаковки вогнутых фигур, таких как [[Звёздчатый многоугольник|звёздчатые многоугольники]], может быть произвольно малой.

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

==Упаковки на плоскости==
[[Файл:Circle packing (hexagonal).svg|160px|thumb|right|Одинаковые круги в ''шестиугольной упаковке'', самая плотная упаковка.]]
[[Файл:Order and Chaos.tif|thumb|Шестиугольная упаковка  естественного расположения одинаковых кругов  с переходом на нерегулярное расположение неравных кругов.]]

Для двумерного евклидова пространства [[Лагранж, Жозеф Луи|Жозеф Луи Лагранж]] доказал в 1773, что решётчатая упаковка кругов высшей плотности — это [[Шестиугольник|шестиугольная]] упаковка<ref name="ChangWang"/>, в которой центры кругов располагаются на [[Шестиугольная решётка|шестиугольной решётке]] (расположенные зигзагом ряды, подобные [[Пчелиные соты|сотам]]), а каждый круг окружён шестью другими окружностями. Плотность такой упаковки равна

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

[[Туэ, Аксель|Аксель Туэ]] привёл первое доказательство, что эта упаковка оптимальна в 1890, показав,что шестиугольная решётка является самой плотной из всех возможных упаковок кругов, как регулярных, так и нерегулярных.  Однако это доказательство считалось не вполне полным.  Первое полноценное доказательство  приписывается [[Фейеш Тот, Ласло|Ласло Фейеш Тоту]] (1940) <ref name="ChangWang">{{cite arXiv |last1=Chang |first1=Hai-Chau |last2=Wang |first2=Lih-Chung |eprint=1009.4322 |title=A Simple Proof of Thue's Theorem on Circle Packing |class=math.MG |date=2010 }}</ref>.

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

=== Однородные упаковки ===
Существует 11 упаковок кругов на основе 11 [[Однородная мозаика#Однородные мозаики на евклидовой плоскости|однородных мозаик]] плоскости{{sfn|Williams|1979|с=35-39}}. В этих упаковках любая окружность может быть отображена на любую другую окружность путём отражения или вращения. [[Шестиугольник|Шестиугольные]] промежутки могут быть заполнены одним кругом, а [[Двенадцатиугольник|двенадцатиугольные]] промежутки могут быть заполнены 7 кругами, образуя 3-однородные упаковки. {{не переведено 5|Усечённая тришестиугольная мозаика|||truncated trihexagonal tiling}} с обоими типами промежутков могут быть заполнена как 4-однородная упаковка. [[Плосконосая тришестиугольная мозаика]] имеет две зеркальные формы.
{| class=wikitable
|+ 1-однородные упаковки, основанные на однородных мозаиках
|- align=center
|[[Файл:triangular tiling circle packing.png|180px]]<BR>[[Треугольный паркет|Треугольная]]
|[[Файл:Square tiling circle packing.png|180px]]<BR>[[Квадратный паркет|Квадратная]]
|[[Файл:Hexagonal tiling circle packing.png|180px]]<BR>[[Шестиугольный паркет|Шестиугольная]]
|[[Файл:Elongated triangular tiling circle packing.png|180px]]<BR>{{не переведено 5|Удлинённая треугольная мозаика|Удлинённая треугольная||Elongated triangular tiling}} 
|- align=center
|[[Файл:Trihexagonal tiling circle packing.png|180px]]<BR>[[Тришестиугольная мозаика|Тришестиугольная]]
|[[Файл:Snub square tiling circle packing.svg|180px]]<BR>[[Плосконосая квадратная мозаика|Плосконосая квадратная]]
|[[Файл:Truncated square tiling circle packing.png|180px]]<BR>[[Усечённая квадратная мозаика|Усечённая квадратная]]
|[[Файл:Truncated hexagonal tiling circle packing.png|180px]]<BR>{{не переведено 5|Усечённая шестиугольная мозаика|Усечённая шестиугольная||Truncated hexagonal tiling}}
|- align=center
|[[Файл:Rhombitrihexagonal tiling circle packing.png|180px]]<BR>{{не переведено 5|Ромботришестиугольная мозаика|Ромботришестиугольная||Rhombitrihexagonal tiling}}
|[[Файл:Snub hexagonal tiling circle packing.png|180px]]<BR>[[Плосконосая тришестиугольная мозаика|Плосконосая шестиугольная]]
|[[Файл:Snub hexagonal tiling mirror circle packing.png|180px]]<BR>Плосконосая шестиугольная (зеркальная)
|[[Файл:Truncated rhombitrihexagonal tiling circle packing.png|180px]]<BR>{{не переведено 5|Усечённая тришестиугольная мозаика|Усечённая тришестиугольная||Truncated trihexagonal tiling}}
|}

==Упаковка на сфере==
Связанная задача — определение расположения с минимальной энергией одинаково расположенных точек, которые должны лежать на заданной поверхности.
[[Задача Томсона]] рассматривает распределение электрических зарядов с наименьшей энергией на поверхности сферы.
{{не переведено 5|Задача Таммеса|||Tammes problem}} является обобщением этой задачи и максимизирует минимальное расстояние между кругами на сфере.

==Упаковка в ограниченных областях==
[[Файл:Circles packed in square 15.svg|thumb|right|Пятнадцать одинаковых кругов, [[Упаковка кругов в квадрате|упакованных в наименьший возможный квадрат]]. Только четыре равносторонних треугольника образуются соприкасающимися кругами.]]
{{main|Упаковка кругов в круге}}
{{main|Упаковка кругов в квадрате}}
{{main|Упаковка кругов в правильном треугольнике}}
{{main|Упаковка кругов в равнобедренном прямоугольном треугольнике}}
[[Задачи упаковки|Упаковка кругов]] в простых ограниченных фигурах является общим типом задач [[Развлекательная математика|занимательной математики]].  Влияние стен контейнера важно, и шестиугольная упаковка в общем случае не является оптимальной для малого числа кругов.

==Неравные круги==
[[Файл:2-d dense packing r1.svg|thumb|left|Компактная упаковка бинарных кругов с наиболее близкими размерами кругов{{sfn|Kennedy|2006|с=255–267}}. Упаковка также является самой плотной упаковкой кругов  с этим отношением размеров (отношение 0.6375559772 с отношением упаковки (плотности) 0.910683){{sfn|Heppes|2003|с=241–262}}]]
Существует также ряд задач, которые разрешают размеры кругов быть неоднородными. Одним из таких расширений является задача нахождения максимально возможной плотности системы с двумя размерами кругов (''бинарная'' система).  Только девять определённых отношений радиусов позволяют ''компактную упаковку'', в которой, если две окружности касаются, они вместе касаются также ещё двух кругов (если соединить отрезками центры касающихся окружностей, они триангулируют поверхность){{sfn|Kennedy|2006|с=255–267}}. Для семи таких отношений радиусов известны компактные упаковки, на которых достигается максимальное возможное отношение упаковки (выше, чем для кругов одного диаметра) для смеси кругов данного отношения радиусов. Высшая плотность упаковки — 0.911627478 для отношения радиусов 0.545151042•{{sfn|Heppes|2003|с=241–262}}{{sfn|Kennedy|date=21 Dec 2004}}.

Также известно, что если отношение радиусов выше 0.742, бинарная смесь не может быть упакована лучше, чем круги одного размера{{sfn|Heppes|2003|с=241–262}}. Верхние границы, которые могут быть достигнуты такой бинарной упаковкой для меньших отношений радиусов, также получены{{sfn|de Laat, de Oliveira Filho, Vallentin}}. 
{{clear}}

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

Упаковка окружностей стала существенным средством в искусстве [[оригами]], так как каждая часть в фигуре оригами требует круг на листе бумаге <ref>Лекции по современному оригами "[http://www.ted.com/index.php/talks/robert_lang_folds_way_new_origami.html Robert Lang on TED] {{Wayback|url=http://www.ted.com/index.php/talks/robert_lang_folds_way_new_origami.html |date=20111015121117 }}."</ref>.  [[Лэнг, Роберт|Роберт Лэнг]] использовал математику упаковки кругов для разработки компьютерных программ, предназначенных для разработки сложных фигур оригами.

== См. также ==
{{кол|2}}
* [[Плотная упаковка равных сфер]]
* [[Сетка Аполлония]]
* {{не переведено 5|Упаковка кругов в квадрате|||Circle packing in a square}}
* {{не переведено 5|Инвертируемое расстояние|||Inversive distance}}
* [[Упаковка кругов в круге]]
* [[Гипотеза Кеплера]]
* [[Окружности Мальфатти]]
* [[Задачи упаковки]]
* [[Контактное число]]{{конец кол}}

==Примечания==
{{примечания|2}}

==Литература==
* {{книга 
|автор= Wells D 
|год= 1991 
|заглавие= The Penguin Dictionary of Curious and Interesting Geometry 
|издательство= Penguin Books 
|место= New York 
|isbn= 0-14-011813-6 
|страницы= 30-31, 167
}}
*{{статья
|автор=Tom Kennedy
|ref=Kennedy
|заглавие=Compact packings of the plane with two sizes of discs
|год=2006
|страницы=255–267
|том=35
|издание=Discrete and Computational Geometry|arxiv=math/0407145v2
|doi=10.1007/s00454-005-1172-4
|issue=2}}
* {{статья
|автор=Aladár Heppes
|ref=Heppes
|заглавие=Some Densest Two-Size Disc Packings in the Plane|journal=Discrete and Computational Geometry
|дата=1 August 2003
|год=2003
|том=30
|выпуск=2
|страницы=241–262
|doi=10.1007/s00454-003-0007-6
}}
*{{книга
|автор=Robert Williams
|ref=Williams
|год=1979
|заглавие=The Geometrical Foundation of Natural Structure: A Source Book of Design
|ссылка=https://archive.org/details/geometricalfound00will
|издательство=Dover Publications, Inc.
|ISBN=0-486-23729-X
}}
* {{статья
|автор=Kenneth Stephenson
|ref=Stephenson
|заглавие=Circle Packing: A Mathematical Tale
|издание=[[Notices of the American Mathematical Society]]
|год= 2003
|том=50
|выпуск=11
|url=http://www.math.utk.edu/~kens/Notices_article.pdf
}}
*{{cite web
|url=http://arxiv.org/abs/math/0412418
|author=Tom Kennedy
|ref=Kennedy
|title=A densest compact planar packing with two sizes of discs
|date=2004-12-21
|accessdate=2016-06-07
}}
*{{cite web
|author=David de Laat, Fernando Mario de Oliveira Filho, Frank Vallentin  
|ref=de Laat, de Oliveira Filho, Vallentin  
|title=Upper bounds for packings of spheres of several radii
|url=http://arxiv.org/abs/1206.2608
|accessdate=2016-06-07
|date=2012-06-12
}}

{{Задачи упаковки|state=collapsed}} 
{{rq|checktranslate|style}}


[[Категория:Задачи упаковки]]