30
правок
Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
Взглянем на планарный граф множества(рис.2) прямых. Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро, которая принадлежит нижней части планарного графа(именно той, что задаёт часть пересечения полуплоскостей).
Вернемся к <tex>\mathcal{UH}</tex> и заметим, что при обходе цепи, координата <tex>X</tex> точек Х растет. Если же мы будет обходить цепочку из <tex>P</tex>, образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. Учитывая этот факт, и то что наклон линии из <tex>\mathcal{LE}</tex> совпадет с <tex>X </tex> координатой точки(вспоминаем отображение и применяем производную), можно сделать вывод, что обход слева направо точек из цепи <tex>\mathcal{UH}</tex>, совпадает с обходом точек из <tex>\mathcal{LE}</tex> справа налево. (Обе линии монотоны, одна возрастает, другая убывает. Количество точек в массиве одинаковое, при это каждая точка из <tex>\mathcal{UH}</tex> внесла вклад в <tex>\mathcal{LE}</tex>)
}}
