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

Материал из Викиконспекты
Перейти к: навигация, поиск
Пример отображения

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

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

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

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

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

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

Замечания:

  • [math] D(D(P)) = P [/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] \exists l \forall i : p_i [/math] лежит под [math] l [/math] и [math] l [/math] не вертикальна.

Таким образом получаем:

  • Взаимно однозначное соответствие между вершинами [math] CH(D(L)) [/math] и границами пересечения [math] \cap_{i=1}^{n}(l_i) [/math];
  • Порядок точек в [math] CH(D(L)) [/math] совпадает с порядком прямых в пересечении.

Источники