Изменения

Перейти к: навигация, поиск

Диаграмма Вороного

48 байт добавлено, 21:16, 14 мая 2015
Свойства
{{Лемма
|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.
|proof=[[Файл:voronoi-farthest-inside.png|200px|right]]Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки.
Пусть самый удалённый от точки <tex>q</tex> сайт <tex>pp_i</tex> не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём окружность с центром в луч <tex>qp_i</tex>, проходящую через . Он пересечёт ребро выпуклой оболочки <tex>pp_j p_k</tex>. Так как <tex>p</tex> — внутри выпуклой оболочкиПолучатся два смежных угла, рассмотрим тот, эта окружность пересечёт оболочку который оказался прямым или полностью лежит внутри неётупым. Тогда вне окружности должен лежать какой-то сайт <tex>p_i</tex>. Но тогда в полученном треугольнике <tex>\rho(q, p_ip_j) > \rho(q, pp_i)</tex>, так как напротив большего угла лежит большая сторона. Пришли к противоречию.
}}
418
правок

Навигация