222
правки
Изменения
м
Рассмотрим отображение <tex> D </tex> между точками и прямыми, такое что:
<tex> D(P(k, b)) = (Y = kX - b) </tex>
<tex> D(Y = kX + b) = P(k, -b) </tex>
Это отображение не рассматривает вертикальные прямые, поэтому их мы рассмотрим в конце отдельно.
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
Будем обозначать, что <tex> D(p) = p^* </tex>, <tex> D(l) = l^* </tex>
Факт дуализма:
* Точка <tex> p </tex> лежит под/на/над прямой <tex> l </tex> тогда и только тогда, когда <tex> D(l) </tex> лежит под/на/над прямой <tex> D(p) </tex>;
Тогда точка <tex> p \in P = \cup p_i </tex> принадлежит <tex> UH(P) </tex> тогда и только тогда, когда существует такая не вертикальная прямая <tex> l </tex>, что <tex> \forall i : p_i </tex> лежит под <tex> l </tex>.
Перефразируем для dual-пространства:
* Существует точка <tex> l^* </tex> на прямой <tex> p^* \in P^* : l^* </tex> лежит под любой прямой из <tex> P^*</tex>.
Рассмортим верхний конвекс-халл точек <tex> P </tex> (англ. ''upper convex hull'') и нижнюю огибающей прямых <tex> P^* </tex> (англ. ''lower envelope''). Точки в <tex> P </tex> появляются в <tex> UH(P) </tex> по увелечению х-координаты. Прямые в <tex> P^* </tex> появляются в <tex> LE(P^*) </tex> по уменьшению угла наклона. Так как угол наклона соответствует х-координате, то список точек <tex> UH(P) </tex> слева-направо соответствует списку справа-налево ребер <tex> LE(P^*) </tex>. Таким образом верхний конвекс-халл соответствует нижней огибающей прямых. Аналогично для нижнего СН и верхней огибающей.
Более формально: точки <tex> p, q \in P : pq </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>
Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халла.
Нет описания правки
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
[[Файл:halfSpaces.png|400px|thumb|right|Нужна ли нам верхняя полуплоскость<tex> l'' </tex>?]]
Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.
От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и пересекаются.
== Источники ==
