|
|
 |
Условие
Любую конечную систему точек плоскости можно покрыть несколькими непересекающимися кругами, сумма диаметров которых меньше количества точек и расстояние между любыми двумя из которых
Расстояние между двумя кругами — это расстояние между их ближайшими точками.
Решение
Нам понадобится следующая очевидная лемма.
Если два круга диаметров d1 и d2 пересекаются (имеют
общую точку), то их можно заключить в один круг диаметра не больше
d1+d2 (рис. 7 а, б ).
Построим круг с центром в каждой из данных N точек, имеющий радиус a
( a несколько больше 1/2 ; точнее значение a выберем ниже). Если
среди этих кругов окажутся пересекающиеся, то, пользуюсь леммой, заменим
какие-либо два пересекающихся круга (все равно какие) одним покрывающим
их кругом. Если среди полученных кругов еще есть пересекающиеся, снова
воспользуемся леммой, и т.д. Пусть вообще есть какая-то система кругов,
которые: 1) покрывают все данные точки вместе с кругами радиуса a
с центрами в этих точках и 2) имеют сумму диаметров не больше N · 2a .
Тогда если среди них есть пересекающиеся, то мы можем воспользоваться
леммой и построить новую систему из меньшего количества кругов,
удовлетворяющую тем же условиям 1), 2), и так до тех пор, пока мы не
получим такой системы из k кругов, никакие два из которых не пересекаются.
Уменьшим теперь радиус каждого из этих k кругов на величину b , оставив
их центры на месте ( b больше 1/2 и меньше a ; точное значение b
указано ниже). Тогда полученные k кругов:
1) содержат все данные точки,
2) имеют сумму диаметров не больше N · 2a-k · 2b 2Na-2b ,
3) отстоят друг от друга не меньше чем на 2b .
Ясно, что если выбрать a и b так, чтобы выполнялись неравенства
b; 2Na-2b
