Пересечение полуплоскостей, связь с выпуклыми оболочками

Пример отображения

Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.

Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство — Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)

Рассмотрим отображение [math] D [/math] между точками и прямыми, такое что:

[math] D(P(k, b)) = (Y = kX - b) [/math]

[math] D(Y = kX + b) = P(k, -b) [/math]

Совпадение верхнего CH и нижней огибающей

Будем обозначать, что [math] D(p) = p^* [/math], [math] D(l) = l^* [/math]

Факт дуализма:

• Точка [math] p [/math] лежит под/на/над прямой [math] l [/math] тогда и только тогда, когда [math] D(l) [/math] лежит под/на/над прямой [math] D(p) [/math];

Тогда точка [math] p \in P = \cup p_i [/math] принадлежит [math] UH(P) [/math] тогда и только тогда, когда существует такая не вертикальная прямая [math] l [/math], что [math] \forall i : p_i [/math] лежит под [math] l [/math].

Перефразируем для dual-пространства:

• Существует точка [math] l^* [/math] на прямой [math] p^* \in P^* : l^* [/math] лежит под любой прямой из [math] P^*[/math]

Источники

• Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 11 page 253-254
• http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf