30
правок
Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).
Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) => \Rightarrow P^\star (p_x x - p_y)</tex>.
Далее воспользуемся основными свойствами дуальной трансформации (см. доказательтсво в конспекте о [[двойственное пространство|двойственном прострастве]]):
[[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]]
Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull).
По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой.
Рассмотрим какую-то точку <tex>p^\star \in P^\star</tex> и заметим, что она будет принадлежать цепи <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> <tex>\exists</tex> прямая <tex>l^\star </tex> : <tex>p^\star \in l^\star</tex> и все точки из <tex>P^\star</tex> лежат ниже <tex>l^\star</tex> (сейчаc мы жили в двойственном пространстве). В обычном пространстве данный факт эквивалентен следующему:
Итого: у нас есть точка <tex>l</tex> на прямой <tex>p</tex>, лежащая ниже всех остальных прямых из <tex>P</tex>.
}}
