Изменения

{{Определение|definition=Диаграмма <tex>n - 1</tex>-го порядка является farthest-point диаграммой, т.е. в каждой её ячейке все точки являются наиболее удалёнными от какого-то сайта.}} === Построение ===Для построения ячейки farthest-point диаграммы для <tex>p_i</tex> будем пересекать полуплоскости, не содержащие <tex>p_i</tex>, образованные серединными перпендикулярами между <tex>p_i</tex> и остальными сайтами (то есть аналогично обычной диаграмме Вороного, но для пересечения берутся противоположные полуплоскости).  === Свойства ==={{Утверждение|statement=Все ячейки farthest-point диаграммы выпуклы.|proof=По построению ячейка — пересечение полуплоскостей, значит, она выпукла.}} {{Лемма|statement=Для любой точки <tex>q</tex> плоскости самый удалённый от неё сайт из <tex>P</tex> должен лежать на [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull|выпуклой оболочке]] <tex>P</tex>.|proof=Сайт, не находящийся на выпуклой оболочке, лежит внутри неё по свойствам выпуклой оболочки. Пусть самый удалённый от точки <tex>q</tex> сайт <tex>p</tex> не лежит на выпуклой оболочке (т.е. лежит внутри неё). Проведём окружность с центром в <tex>q</tex>, проходящую через <tex>p</tex>. Так как <tex>p</tex> — внутри выпуклой оболочки, эта окружность пересечёт оболочку или полностью лежит внутри неё. Тогда вне окружности должен лежать какой-то сайт <tex>p_i</tex>. Но тогда <tex>\rho(q, p_i) > \rho(q, p)</tex>. Пришли к противоречию.}} {{Лемма|statement=Сайт, который лежит внутри выпуклой оболочки сайтов, не может иметь ячейку в farthest-point диаграмме.|proof=}} {{Лемма|statement=Каждый сайт, который является вершиной выпуклой оболочки сайтов, имеет ячейку в farthest-point диаграмме.|proof=Докажем по индукции. База индукции: для двух сайтов они оба являются вершинами выпуклой оболочки и оба имеют ячейку в farthest-point диаграмме (дальняя от сайта полуплоскость). Переход: добавим сайт <tex>p</tex> так, что он станет новой вершиной выпуклой оболочки. Пусть он не имеет ячейку в farthest-point диаграмме, то есть уже имеющаяся перед его добавлением диаграмма не меняется. Для построения farthest-point диаграммы проводятся серединные перпендикуляры между всеми парами сайтов, и полученные полуплоскости пересекаются; раз новой ячейки не добавилось, то серединные перпендикуляры между <tex>p</tex> и остальными сайтами совпали с уже имеющимися перпендикулярами. Это возможно, только если <tex>p</tex> совпал с другим сайтом. Пришли к противоречию.}}