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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 11: Строка 11:
 
<tex> D(Y = kX + b) = P(k, -b) </tex>
 
<tex> D(Y = kX + b) = P(k, -b) </tex>
  
Обозначим <tex> L = \{l_1, l_2, ... , l_n\} </tex> {{---}} множество прямых.
+
Обозначим <tex> L = \{l_1, l_2, ... , l_n\} </tex> {{---}} множество прямых. Сначала рассмотрим случай, когда пересечение не пусто и содержит точку <tex> O </tex>. Тогда исходные полуплоскости <tex> h_i </tex> {{---}} это прямая <tex> l_i </tex> и полуплоскость, содержащая <tex> O </tex>.
  
 
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
 
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]

Версия 19:55, 21 февраля 2014

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

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

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

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

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

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

Обозначим [math] L = \{l_1, l_2, ... , l_n\} [/math] — множество прямых. Сначала рассмотрим случай, когда пересечение не пусто и содержит точку [math] O [/math]. Тогда исходные полуплоскости [math] h_i [/math] — это прямая [math] l_i [/math] и полуплоскость, содержащая [math] O [/math].

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

Замечания:

  • [math] D(D(P)) = P [/math]
  • Точка [math] p [/math] лежит на прямой [math] l_i [/math] тогда и только тогда, когда [math] D(l_i) [/math] лежит на прямой [math] D(p) [/math];
  • Прямая [math] l_i [/math] лежит на границе пересечения тогда и только тогда, когда [math] D(l_i) [/math] — экстремальная точка [math] D(L) [/math];
  • Точка [math] l_i [/math] вершина пересечения прямых [math] l_i [/math] и [math] l_j [/math] тогда и только тогда, когда [math] l(D(l_i), D(l_j)) [/math] —опорное ребро конвекс халла [math] CH(D(L)) [/math];
  • Точка [math] l_i [/math] — не экстемальная точка [math] D(L) [/math] тогда и только тогда, когда удаление [math] h_i [/math] не повлияет на пересечение.

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

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

Источники