Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
{{Лемма
|id=1
|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходным исходных полуплоскостей
|proof=
'''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение.
Рассмотрим планарный случай и предположим, что вертикальный вертикальные прямые отсутствуюотсутствуют (в конце приведем два способа решения данной проблемы).
Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).
Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) => 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>
}}
Утверждение выше может быть выведено из '''[[двойственное пространство|двойственного простраства]].'''
== Источники ==
