30
правок
Изменения
→Связь пересечения полуплоскостей с выпуклой оболочкой
'''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение.
'''Важно2Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO
Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы).
#<tex>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex>
'''Важно 2:'''
* <tex>p^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,
* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,
* Значок <tex>*</tex> означает, что элемент из двойственного пространства.
Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку.
По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой.
