30
правок
Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).
Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) \Rightarrow P^\star (p_x x - p_y)</tex>.
Далее воспользуемся основными свойствами дуальной трансформации (см. доказательтсво в конспекте о [[двойственное пространство|двойственном прострастве]]):
#<tex>p</tex> <tex>\in</tex> <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> <tex>\in</tex> <tex>p^\star</tex>, где <tex>p</tex> - точка в исходном пространстве, <tex>l</tex> - прямая в исходном пространстве, <tex>l^\star</tex>, <tex>p^\star</tex> - их дуальное отображение.
#<tex>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex>
Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку.
По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой.
Итого: у нас есть точка <tex>l</tex> на прямой <tex>p</tex>, лежащая ниже всех остальных прямых из <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>)
Напоследок, cоседние точки <tex>p^\star</tex> и <tex>q^\star</tex> из <tex>P^\star</tex> образуют какое-то или принадлежат какому-то ребру <tex>\mathcal{UH}</tex> <tex>Leftrightarrow</tex>
все точки из <tex>P^\star</tex> лежат "ниже" линии, построенной на точках <tex>p^\star</tex> и <tex>q^\star</tex>. В исходном пространстве это означает: все прямые из пространства <tex>P</tex> за исключением прямых <tex>p</tex> и <tex>q</tex> лежат над пересечением <tex>p</tex> и <tex>q</tex>. Это достаточное условие, что пересечение <tex>p</tex> и <tex>q</tex> <tex>\in</tex> <tex>\mathcal{LE}</tex>.
}}
