Задача 79323
|
|
 |
Условие
На плоскости задано конечное множество точек. Доказать, что в нём найдётся точка, у которой имеется не более трёх ближайших к ней точек из этого же множества.Решение
Предположим, что мы построили такое множество M точек на плоскости, в котором у каждой не менее четырёх ближайших. Пусть r — наименьшее из расстояний между его точками. Рассмотрим множество L ⊂ M всех точек, расстояние от которых до ближайших к ним равно r; в множестве L, очевидно, также у каждой точки будет не менее четырёх ближайших.Построим выпуклую оболочку K множества L (наименьший выпуклый многоугольник, содержащий L). Пусть A — одна из крайних точек L, то есть одна из вершин K. Пусть B1, B2, B3, B4 — четыре точки из L, находящиеся на расстоянии r от A. Ясно, что любой из углов
