Задача 58070

Тема:    [ Выпуклая оболочка и опорные прямые (плоскости) ]

Сложность: 5 Классы: 8,9

Условие

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

Решение

Выберем наименьшее из всех попарных расстояний между данными точками и рассмотрим точки, у которых есть соседи на таком расстоянии. Достаточно доказать требуемое утверждение для этих точек. Пусть P — вершина их выпуклой оболочки. Если A_i и A_j — ближайшие к P точки, то A_iA_jA_iP и  A_iA_jA_jP, поэтому A_iPA_j60^o. Следовательно, у точки P не может быть четырех ближайших соседей, так как иначе один из углов A_iPA_j был бы меньше 180^o/3 = 60^o. Поэтому P — искомая точка.

Источники и прецеденты использования

книга
Автор	Прасолов В.В.
Год издания	2001
Название	Задачи по планиметрии
Издательство	МЦНМО
Издание	4*
глава
Номер	20
Название	Принцип крайнего
Тема	Принцип крайнего
параграф
Номер	5
Название	Выпуклая оболочка и опорные прямые
Тема	Выпуклая оболочка и опорные прямые (плоскости)
задача
Номер	20.024