Условие
Озеро имеет форму невыпуклого
n-угольника. Докажите, что множество точек озера, из которых видны все его берега, либо пусто, либо заполняет внутренность выпуклого
m-угольника, где
m≤n.
Решение
Итак, имеется несамопересекающийся невыпуклый
n-угольник
P. Рассмотрим множество
T его внутренних точек, из которых видны все вершины
P. Докажем, что
T — выпуклый многоугольник, число сторон которого не больше
n.
Каждой стороне AB многоугольника P поставим в соответствие полуплоскость,
граница которой есть прямая AB (из двух таких полуплоскостей мы выбираем ту,
которая содержит достаточно близкие к AB внутренние точки многоугольника P).
Число таких полуплоскостей равно числу сторон P, что равно n. Тем самым,
в пересечении всех таких полуплоскостей получается выпуклый многоугольник T
с количеством сторон не большим n.
Докажем, что многоугольник T и является искомым. Во-первых, заметим, что
если точка не содержится в какой-нибудь из рассмотренных полуплоскостей,
то из неё не видно одной из вершин соответствующей стороны.
Во-вторых, докажем, что из любой точки многоугольника T видны все вершины
многоугольника P. Предположим противное.
Пусть точка B принадлежит T, но из B не видно вершину A. Это значит,
что отрезок AB пересекает стороны многоугольника P. Если часть отрезка AB, прилегающая к вершине A, лежит вне многоугольника, то точка B не принадлежит полуплоскости, соответствующей стороне многоуголника с вершиной A. Иначе рассмотрим сторону
многоугольника ближайшую к точке A и пересекающую AB, тогда точка B не
принадлежит полуплоскости, соответствующей этой стороне. Получили
противоречие.
Источники и прецеденты использования
