222
правки
Изменения
м
Нет описания правки
[[Файл:duality.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
[[Файл:duality.png|400px|thumb|right|Пример отображения]]
Точки в <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> 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>Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халла.
== Источники ==
