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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м
Строка 6: Строка 6:
 
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
 
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
  
Пусть у нас прямые заданы уравнениями вида <tex> Ax + By + C = 0 </tex>. Тогда предикат проверки того, что прямая <tex> l'' : A''x + B''y + C'' = 0 </tex> лежит над пересечением прямых <tex> l : Ax + By + C = 0 </tex> и <tex> l' : A'x + B'y + C' = 0 </tex> будет равен:
+
Пусть у нас прямые заданы уравнениями вида <tex> Ax + By + C = 0 </tex>. Тогда предикат(см. рисунок) проверки того, что прямая <tex> l'' : A''x + B''y + C'' = 0 </tex> лежит над пересечением прямых <tex> l : Ax + By + C = 0 </tex> и <tex> l' : A'x + B'y + C' = 0 </tex> будет равен <tex>
<tex>
 
 
\begin{vmatrix}  
 
\begin{vmatrix}  
 
A & B & C \\  
 
A & B & C \\  
Строка 15: Строка 14:
 
</tex>.  
 
</tex>.  
  
Докажем это. Для проверки предиката нам надо определить знак <tex> A''x_0 + B''y_0 + C'' </tex>, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>. Эту точку можно найти из уравнения <tex>
+
Докажем это. Для проверки предиката нам надо определить знак выражения <tex> A''x_0 + B''y_0 + C'' </tex>, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>. Эту точку можно найти из уравнения <tex> \begin{pmatrix}  
\begin{pmatrix}  
 
 
A & B\\  
 
A & B\\  
 
A' & B'  
 
A' & B'  
Строка 28: Строка 26:
 
-C'  
 
-C'  
 
\end{pmatrix}
 
\end{pmatrix}
</tex>.  
+
</tex>. Решением будет <tex>
 
 
<tex>
 
 
\begin{pmatrix}  
 
\begin{pmatrix}  
 
x_0\\  
 
x_0\\  
Строка 50: Строка 46:
 
\end{vmatrix}
 
\end{vmatrix}
 
}
 
}
</tex>. Подставим это решение в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель:
+
</tex>. Подставим его в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель.
  
 
<tex> A'' (B'; -B)(-C; -C') + B'' (-A'; A)(-C; -C') + C \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} = A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} - B'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} + C'' \begin{vmatrix} A & A' \\ B & B' \end{vmatrix} = \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -C'' & -C' & -C \end{vmatrix} = \begin{vmatrix} A & B & C \\  
 
<tex> A'' (B'; -B)(-C; -C') + B'' (-A'; A)(-C; -C') + C \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} = A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} - B'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} + C'' \begin{vmatrix} A & A' \\ B & B' \end{vmatrix} = \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -C'' & -C' & -C \end{vmatrix} = \begin{vmatrix} A & B & C \\  
Строка 56: Строка 52:
 
A'' & B'' & C'' \end{vmatrix} </tex>
 
A'' & B'' & C'' \end{vmatrix} </tex>
  
Таким образом если представить прямую <tex> Ax + By + C = 0 </tex> как точку с координатами <tex> (A, B, C) </tex>, где <tex> C </tex> {{---}} однородная координата, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} обход Грэхема.
+
Таким образом если представить прямую <tex> Ax + By + C = 0 </tex> как точку с координатами <tex> (A, B, C) </tex>, где <tex> C </tex> {{---}} однородная координата, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обход Грэхема]] для нахождения выпуклой оболочки.
  
  

Версия 19:31, 5 апреля 2014

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

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

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

Пусть у нас прямые заданы уравнениями вида [math] Ax + By + C = 0 [/math]. Тогда предикат(см. рисунок) проверки того, что прямая [math] l'' : A''x + B''y + C'' = 0 [/math] лежит над пересечением прямых [math] l : Ax + By + C = 0 [/math] и [math] l' : A'x + B'y + C' = 0 [/math] будет равен [math] \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix} [/math].

Докажем это. Для проверки предиката нам надо определить знак выражения [math] A''x_0 + B''y_0 + C'' [/math], где [math] (x_0, y_0) [/math] — точка пересечения прямых [math] l' [/math] и [math] l [/math]. Эту точку можно найти из уравнения [math] \begin{pmatrix} A & B\\ A' & B' \end{pmatrix} \begin{pmatrix} x_0\\ y_0 \end{pmatrix} = \begin{pmatrix} -C\\ -C' \end{pmatrix} [/math]. Решением будет [math] \begin{pmatrix} x_0\\ y_0 \end{pmatrix} = \frac{ \begin{pmatrix} B' & -B\\ -A' & A \end{pmatrix} \begin{pmatrix} -C\\ -C' \end{pmatrix}} { \begin{vmatrix} A & B\\ A' & B' \end{vmatrix} } [/math]. Подставим его в [math] A''x_0 + B''y_0 + C'' [/math] и домножим на определитель.

[math] A'' (B'; -B)(-C; -C') + B'' (-A'; A)(-C; -C') + C \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} = A'' \begin{vmatrix} B' & B \\ -C' & -C \end{vmatrix} - B'' \begin{vmatrix} A' & A \\ -C' & -C \end{vmatrix} + C'' \begin{vmatrix} A & A' \\ B & B' \end{vmatrix} = \begin{vmatrix} A'' & A' & A \\ B'' & B' & B \\ -C'' & -C' & -C \end{vmatrix} = \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix} [/math]

Таким образом если представить прямую [math] Ax + By + C = 0 [/math] как точку с координатами [math] (A, B, C) [/math], где [math] C [/math] — однородная координата, то этот предикат — всего лишь поворот, а проверка предиката — обход Грэхема для нахождения выпуклой оболочки.



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

Более формально: точки [math] p, q \in P : pq [/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]

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

Источники