§ 4. Заполнение и покрытие выпуклой области равными кругами

Область, равными экземплярами которой можно покрыть плоскость без пробелов и двойных покрытий, мы назовем замещающей областью. Каждый треугольник, четырехугольник или центрально-симметричный шестиугольник является замещающей областью. Для четырехугольника это обстоятельство вытекает из того, что каждый (не обязательно выпуклый!) четырехугольник можно дополнить до центрально - симметричного шестиугольника — для этого достаточно отразить его симметрично от середины одной из его сторон (рис. 61). Рисунки 62—67 дают нам другие примеры замещающих областей.

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

Рис. 61.

Рис. 62.

Рис. 63.

Рис. 64.

Рис. 65.

Рис. 66.

Рис. 67.

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

Интересно отметить, что из неравенств (2,1) и (2,2), которые можно рассматривать как асимптотические оценки для больших областей, следуют аналогичные оценки для любого (сколь угодно малого!) квадрата. И наоборот, из подобных оценок плотности заполнения и покрытия хотя бы одной замещающей области следуют неравенства (2,1) и (2,2) [62].

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

Если в выпуклой области Т расположены по крайней мере два равных непересекающихся круга, то сумма их площадей

Если выпуклая область Т покрыта по крайней мере двумя равными кругами, то сумма их площадей

Из этих теорем, в частности, вытекает, что числа А и а единичных кругов, которыми можно покрыть произвольно заданную выпуклую область, соответственно, которыми можно заполнить эту область, связаны неравенством (здесь исключается из рассмотрения тот особый случай, когда область сама есть единичный круг и . Так, например, если для покрытия выпуклой области достаточно 100 единичных кругов, то в этой области можно расположить не больше 74 непересекающихся единичных кругов.

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

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

Рис. 68.

Из доказанного следует, что

откуда и вытекает неравенство (1).

Положим теперь, что единичные круги полностью покрывают область Т.

При этом можно считать, что ни один из кругов не является лишним, т. е. ни один нельзя отбросить без того, чтобы оставшиеся круги не перестали покрывать Т. Разложим Т, как выше, на выпуклые части ТА и примем их за грани вырожденного выпуклого многогранника Р с гранями, где гранью является сама область Т. Мы можем считать, что Р имеет только трехгранные углы, рассматривая случай наличия -гранного угла как предельный, отвечающий совпадению трехгранных углов. Так как число вершин выпуклого многогранника с гранями, имеющего лишь трехгранные углы, равно , то число вершин Р (где -гранная вершина защитывается за равно [64].

Рассмотрим область T и обозначим отрезанные сторонами «сегменты» круга следующие в циклическом порядке, через

Рис. 69.

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

Каждая часть круга которая не лежит ни внутри ни на границе какого-либо сегмента, принадлежит, очевидно, нескольким сегментам, отвечающим смежным сторонам Т в противном случае у нас имелся бы лишний круг. (Рассмотрим, например, точку Q (рис. 69), которая лежит в но вне Здесь круг, отмеченный стрелкой на чертеже, является лишним.) Если, однако, точка лежит в то она лежит одновременно в . Поэтому если мы покроем сегменты бумажными листами и вырежем из них v «треугольников» то часть круга лежащая вне будет покрыта точно один раз. Отсюда следует, что

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

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

Фигурирующему выше равенству можно придать еще и другую форму. Если заметить, что

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

где суммирование распространяется по всем вершинам области Р.

Рис. 70

Выясним теперь, в каком случае достигает минимума площадь области по крайней мере двукратно покрытой тремя кругами или двумя кругами и внешней областью Ко выпуклой области Г (рис. 70). При этом все три области в обоих случаях должны иметь общую точку, и во втором случае можно изменять не только положение кругов, но и саму область

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

Таким образом, в экстремальном случае состоит из шести из четырех) равных сегментов круга, что приводит к неравенствам

Учитывая теперь, что общее число вершин многогранника Р равно имеем:

где - число вершин Р, примыкающих к грани Г. Преобразовывая это неравенство, получаем:

в силу отсюда вытекает также требуемое неравенство (2).