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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 1: Строка 1:
 +
[[Файл:duality.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
 
[[Файл:duality.png|400px|thumb|right|Пример отображения]]
 
[[Файл:duality.png|400px|thumb|right|Пример отображения]]
  
Строка 23: Строка 24:
 
Точки в <tex> P </tex> появляются в <tex> UH(P) </tex> по увелечению х-координаты. Прямые в <tex> P^* </tex> появляются в <tex> LE(P^*) </tex> по уменьшению угла наклона. Так как угол наклона соответствует х-координате, то список точек <tex> UH(P) </tex> слева-направо соответствует списку справа-налево ребер <tex> LE(P^*) </tex>. Таким образом верхний конвекс-халл(англ. ''upper convex hull'') соответствует нижней огибающей прямых(англ ''lower envelope''). Аналогично для нижнего СН и верхней огибающей.
 
Точки в <tex> P </tex> появляются в <tex> UH(P) </tex> по увелечению х-координаты. Прямые в <tex> P^* </tex> появляются в <tex> LE(P^*) </tex> по уменьшению угла наклона. Так как угол наклона соответствует х-координате, то список точек <tex> UH(P) </tex> слева-направо соответствует списку справа-налево ребер <tex> LE(P^*) </tex>. Таким образом верхний конвекс-халл(англ. ''upper convex hull'') соответствует нижней огибающей прямых(англ ''lower envelope''). Аналогично для нижнего СН и верхней огибающей.
  
Более формально: точки <tex> p, q </tex> {{---}} ребро верхнего конвекс-халла тогда и только тогда, когда все остальные точки из <tex> P </tex> лежат ниже прямой, через них проходящей. В dual-пространстве получаем, что <tex> \forall r^*, r \in P </tex> \ <tex> \{p, q\} </tex> лежат над точкой пересечения <tex> p^* </tex> и <tex> q^* </tex>. Это как раз условие, что <tex> p^* \cap q^* </tex> {{---}} вершина <tex> LE(P^*) </tex>.
+
Более формально: точки <tex> p, q </tex> {{---}} ребро верхнего конвекс-халла тогда и только тогда, когда все остальные точки из <tex> P </tex> лежат ниже прямой, через них проходящей. В dual-пространстве получаем, что <tex> \forall r^*, r \in P \setminus \{p, q\} </tex> лежат над точкой пересечения <tex> p^* </tex> и <tex> q^* </tex>. Это как раз условие, что <tex> p^* \cap q^* </tex> {{---}} вершина <tex> LE(P^*) </tex>.
 +
 
 +
Таким образом получаем алгоритм:
 +
* Считаем <tex> H_+ </tex>. (полуплоскости, смотрящие вверх)
 +
* Считаем <tex> H_- </tex>. (полуплоскости, смотрящие вниз)
 +
* Считаем <tex> H_> </tex>. (вертикальные полуплоскости, смотрящие направо)
 +
* Считаем <tex> H_< </tex>. (вертикальные полуплоскости, смотрящие налево)
 +
* Пускаем заметающую вертикальную прямую и получаем пересечение <tex> H_+ \cap H_- \cap H_> \cap H_< </tex>
 +
Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халла.
  
 
== Источники ==
 
== Источники ==

Версия 23:48, 21 февраля 2014

Пересечение существует и выпукло, неограничено или пусто
Пример отображения

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

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

Рассмотрим отображение [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].

Точки в [math] P [/math] появляются в [math] UH(P) [/math] по увелечению х-координаты. Прямые в [math] P^* [/math] появляются в [math] LE(P^*) [/math] по уменьшению угла наклона. Так как угол наклона соответствует х-координате, то список точек [math] UH(P) [/math] слева-направо соответствует списку справа-налево ребер [math] LE(P^*) [/math]. Таким образом верхний конвекс-халл(англ. upper convex hull) соответствует нижней огибающей прямых(англ lower envelope). Аналогично для нижнего СН и верхней огибающей.

Более формально: точки [math] p, q [/math] — ребро верхнего конвекс-халла тогда и только тогда, когда все остальные точки из [math] P [/math] лежат ниже прямой, через них проходящей. В dual-пространстве получаем, что [math] \forall r^*, r \in P \setminus \{p, q\} [/math] лежат над точкой пересечения [math] p^* [/math] и [math] q^* [/math]. Это как раз условие, что [math] p^* \cap q^* [/math] — вершина [math] LE(P^*) [/math].

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

  • Считаем [math] H_+ [/math]. (полуплоскости, смотрящие вверх)
  • Считаем [math] H_- [/math]. (полуплоскости, смотрящие вниз)
  • Считаем [math] H_\gt [/math]. (вертикальные полуплоскости, смотрящие направо)
  • Считаем [math] H_\lt [/math]. (вертикальные полуплоскости, смотрящие налево)
  • Пускаем заметающую вертикальную прямую и получаем пересечение [math] H_+ \cap H_- \cap H_\gt \cap H_\lt [/math]

Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халла.

Источники