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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 46 промежуточных версий 8 участников)
Строка 1: Строка 1:
[[Файл:duality.png|400px|thumb|right|Пересечение существует и выпукло, неограничено или пусто]]
+
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограниченно или пусто]]
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пример отображения]]
 
  
Задача: есть конечное множество полуплоскотей, найти фигуру их пересечения или сообщить что оно пусто.
+
== Предикат трех прямых ==
 +
Задача: есть конечное множество полуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.
  
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскоть выпукла)
+
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскость выпукла)
  
Рассмотрим отображение <tex> D </tex> между точками и прямыми, такое что:
+
Пусть полуплоскости заданы уравнениями прямых и ориентацией, с какой стороны от прямой лежит полуплоскость.
  
<tex> D(P(k, b)) = (Y = kX - b) </tex>
+
Сначала рассмотрим все полуплоскости, которые "смотрят", то есть ориентированны, вниз. Аналогично можно рассмотреть все полуплоскости, которые ориентированны вверх.
  
<tex> D(Y = kX + b) = P(k, -b) </tex>
+
{{Лемма
 +
|statement=
 +
[[Файл:halfSpaces.png|400px|thumb|right|Нужна ли полуплоскость <tex> l'' </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>
 +
\begin{vmatrix}
 +
A & B & C \\
 +
A' & B' & C' \\
 +
A'' & B'' & C''
 +
\end{vmatrix}
 +
</tex>.
 +
|proof=
 +
Для проверки предиката нужно определить знак выражения <tex> A''x_0 + B''y_0 + C'' </tex>, где <tex> (x_0, y_0) </tex> {{---}} точка пересечения прямых <tex> l' </tex> и <tex> l </tex>. Эта точка находится из уравнения <tex> \begin{pmatrix}
 +
A & B\\
 +
A' & B'
 +
\end{pmatrix}
 +
\begin{pmatrix}
 +
x_0\\
 +
y_0
 +
\end{pmatrix} =
 +
\begin{pmatrix}
 +
-C\\
 +
-C'
 +
\end{pmatrix}
 +
</tex>. Решением будет <tex>
 +
\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}
 +
}
 +
</tex>. Подставим это решение в <tex> A''x_0 + B''y_0 + C'' </tex> и домножим на определитель.
  
[[Файл:dual.png|400px|thumb|right|Совпадение верхнего CH и нижней огибающей]]
+
<tex>
Будем обозначать, что <tex> D(p) = p^* </tex>, <tex> D(l) = l^* </tex>  
+
A'' \left<(B'; -B);(-C; -C')\right> + B'' \left<(-A'; A);(-C; -C')\right> + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} =
 +
</tex>
  
Факт дуализма:
+
<tex>
* Точка <tex> p </tex> лежит под/на/над прямой <tex> l </tex> тогда и только тогда, когда <tex> D(l) </tex> лежит под/на/над прямой <tex> D(p) </tex>;
+
= 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} =
Тогда точка <tex> p \in P = \cup p_i </tex> принадлежит <tex> UH(P) </tex> тогда и только тогда, когда существует такая не вертикальная прямая <tex> l </tex>, что <tex> \forall i : p_i </tex> лежит под <tex> l </tex>.
+
</tex>  
  
Перефразируем для dual-пространства:
+
<tex>
* Существует точка <tex> l^* </tex> на прямой <tex> p^* \in P^* : l^* </tex> лежит под любой прямой из <tex> P^*</tex>.
+
= 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} =
 +
</tex>
 +
<tex>
 +
= \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix}
 +
</tex>
 +
}}
  
Точки в <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> Ax + By + C = 0 </tex> как точку с однородными координатами <tex> (A, B, C) </tex>, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.
  
Более формально: точки <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>
+
|id=1
Стоит уточнить, что каждое из этих множеств может быть пусто. Тогда мы не рассматриваем с ним объединение. Однако в результате мы можем получить пустое множество. Это главное отличние пересечения полуплоскостей и конвекс-халла.
+
|statement= Пересечение полуплоскостей может быть получено построением выпуклой оболочки в [[двойственное пространство|двойственном прострастве]] для множества точек, являющихся дуальным преобразованием исходных полуплоскостей
 +
|proof=
 +
[[Файл:DualSpaceCH.png ‎  |400px|thumb|right| Множество точек в двойственном пространстве]]
 +
[[Файл:DualSpaceCH400.png |400px|thumb|right| Множество прямых в исходном пространстве]]
 +
 
 +
'''Важно:''' Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение.
 +
 
 +
'''Важно:''' В картинке перепутаны <tex>P</tex> и <tex>P^\star</tex>. TODO
 +
 
 +
 
 +
Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы).
 +
 
 +
Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость).
 +
Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: <tex> P(p_x, p_y) \Rightarrow P^\star (p_x  x - p_y)</tex>.
 +
 +
Далее воспользуемся основными свойствами дуальной трансформации (см. доказательтсво в конспекте о  [[двойственное пространство|двойственном прострастве]]):
 +
#<tex>p</tex> <tex>\in</tex> <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> <tex>\in</tex> <tex>p^\star</tex>, где <tex>p</tex> - точка в исходном пространстве, <tex>l</tex> - прямая в исходном пространстве, <tex>l^\star</tex>, <tex>p^\star</tex> - их дуальное отображение.
 +
#<tex>p</tex> лежит "над" <tex>l</tex> <tex>\Leftrightarrow</tex> <tex>l^\star</tex> лежит "над" <tex>p^\star</tex>
 +
 
 +
 
 +
'''Важно 2:'''
 +
* <tex>p^\star</tex> - точка в двойственном пространстве, <tex>p</tex> - линия в исходном,
 +
* <tex>l^\star</tex> - прямая в двойственном пространстве, <tex>l</tex> - точка в исходном,
 +
* Значок <tex>*</tex> означает, что элемент из двойственного пространства.
 +
Рассмотрим множество точек(<tex>P^\star</tex>) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за <tex>\mathcal{UH}</tex>(Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку.
 +
По свойству выпуклой оболочки, любое ребро из цепи <tex>\mathcal{UH}</tex> содержит "ниже" себя все точки множества <tex>P^\star</tex>, а так же эта цепь соединяет самую правую точку с самой левой.
 +
 
 +
Рассмотрим какую-то точку <tex>p^\star \in P^\star</tex> и заметим, что она будет принадлежать цепи <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> <tex>\exists</tex> прямая <tex>l^\star </tex> : <tex>p^\star \in l^\star</tex> и все точки из <tex>P^\star</tex> лежат ниже <tex>l^\star</tex> (сейчаc мы жили в двойственном пространстве). В обычном пространстве данный факт эквивалентен следующему:
 +
 +
*Дуальное отображение точки <tex>p^\star</tex> в базовое пространство {{---}} прямая <tex>p</tex>, которая по ''первому свойству'' содержит точку <tex>l</tex>(в базовом пространстве прямая <tex>p^\star</tex> перешла в точку <tex>p</tex>).
 +
*Так как прямая <tex>l^\star</tex> лежит выше всех точек, то теперь каждая прямая из <tex>P</tex> лежит выше точки <tex>l</tex> (по свойству 2).
 +
 
 +
Итого: у нас есть точка <tex>l</tex> на прямой <tex>p</tex>, лежащая ниже всех остальных прямых из <tex>P</tex>.
 +
 
 +
Посмотрим на планарный граф множества(рис.2) прямых. Из факта выше, мы можем понять, что <tex>p</tex> внесла ребро в самый нижний фейс(именно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, как <tex>\mathcal{LE}</tex>. Математически данную цепочку мы можем описать, как минимум из всех линейных функция (заданные прямыми) в <tex>P</tex>. Так же <tex>X</tex> компонента узлов этой цепочки монотонно возрастает.
 +
 
 +
Вернемся к <tex>\mathcal{UH}</tex> и заметим, что при обходе цепи, координата <tex>X</tex> точек  растет. Если же мы будет обходить цепочку из <tex>P</tex>, образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. Учитывая этот факт, и то что наклон линии из <tex>\mathcal{LE}</tex> совпадет с <tex>X</tex>  координатой точки (вспоминаем отображение и применяем производную), можно сделать вывод, что обход слева направо точек из цепи <tex>\mathcal{UH}</tex>, совпадает с обходом точек из <tex>\mathcal{LE}</tex> справа налево.
 +
 
 +
(Обе линии монотоны, одна возрастает, другая убывает. Количество точек в массиве одинаковое, при это каждая точка из <tex>\mathcal{UH}</tex> внесла вклад в <tex>\mathcal{LE}</tex>)
 +
 
 +
Напоследок, cоседние точки <tex>p^\star</tex> и <tex>q^\star</tex> из <tex>P^\star</tex> образуют какое-то или принадлежат какому-то ребру <tex>\mathcal{UH}</tex> <tex>\Leftrightarrow</tex> все точки из <tex>P^\star</tex> лежат "ниже" линии, построенной на точках <tex>p^\star</tex> и <tex>q^\star</tex>. В исходном пространстве это означает: все прямые из пространства <tex>P</tex> за исключением прямых <tex>p</tex> и <tex>q</tex> лежат над пересечением <tex>p</tex> и <tex>q</tex>. Это достаточное условие, что пересечение <tex>p</tex> и <tex>q</tex> <tex>\in</tex> <tex>\mathcal{LE}</tex>.
 +
 
 +
Таким образом мы построили верхнее пересечение полуплоскостей. Аналогичным образом строится нижнее, затем мы пересекаем полученные две цепочки.
 +
}}
 +
Что же делать с вертикальными линиями?
 +
# Найдем все вертикальным прямые за <tex>O(N)</tex>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.
 +
# Перейдем в однородное двойственное пространство.
  
 
== Источники ==
 
== Источники ==
 +
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
 
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 11 page 253-254
 
* Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars (2008), Computational Geometry: Algorithms and Applications (3rd edition), Springer-Verlag, ISBN 978-3-540-77973-5 Chapter 11 page 253-254
* http://wwwisg.cs.uni-magdeburg.de/ag/lehre/SS2012/GAG/slides/V12.pdf
 
 
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 19:05, 4 сентября 2022

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

Предикат трех прямых

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

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

Пусть полуплоскости заданы уравнениями прямых и ориентацией, с какой стороны от прямой лежит полуплоскость.

Сначала рассмотрим все полуплоскости, которые "смотрят", то есть ориентированны, вниз. Аналогично можно рассмотреть все полуплоскости, которые ориентированны вверх.

Лемма:
Нужна ли полуплоскость [math] l'' [/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]\triangleright[/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'' \left\lt (B'; -B);(-C; -C')\right\gt + B'' \left\lt (-A'; A);(-C; -C')\right\gt + C'' \begin{vmatrix} A & B \\ A' & B' \end{vmatrix} = [/math]

[math] = 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} = [/math]

[math] = 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} = [/math]

[math] = \begin{vmatrix} A & B & C \\ A' & B' & C' \\ A'' & B'' & C'' \end{vmatrix} [/math]
[math]\triangleleft[/math]

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

Алгоритм:

  • Отсортировать все полуплоскости по углу наклона;
  • Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);
  • Запустить обход Грэхема для полуплоскостей, смотрящих вверх;
  • Пересечь две цепочки.

От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная — когда обе цепочки не пусты и пересекаются.

Связь пересечения полуплоскостей с выпуклой оболочкой

Лемма:
Пересечение полуплоскостей может быть получено построением выпуклой оболочки в двойственном прострастве для множества точек, являющихся дуальным преобразованием исходных полуплоскостей
Доказательство:
[math]\triangleright[/math]
Множество точек в двойственном пространстве
Множество прямых в исходном пространстве

Важно: Покажем конструктивный алгоритм для множестве полуплоскостей, не содержащих вертикальный полуплоскости. После леммы приведены два рассуждения, позволяющие снять данное ограничение.

Важно: В картинке перепутаны [math]P[/math] и [math]P^\star[/math]. TODO


Рассмотрим планарный случай и предположим, что вертикальные и параллельные прямые отсутствуют (в конце приведем два способа решения данной проблемы).

Пусть у нас есть множество ориентированных прямых, каждая из которых задает полуплоскость(направление вектора нормали задаёт нужную полуплоскость). Тогда каждую плоскость мы можем превратить в точку в двойственном пространстве: [math] P(p_x, p_y) \Rightarrow P^\star (p_x x - p_y)[/math].

Далее воспользуемся основными свойствами дуальной трансформации (см. доказательтсво в конспекте о двойственном прострастве):

  1. [math]p[/math] [math]\in[/math] [math]l[/math] [math]\Leftrightarrow[/math] [math]l^\star[/math] [math]\in[/math] [math]p^\star[/math], где [math]p[/math] - точка в исходном пространстве, [math]l[/math] - прямая в исходном пространстве, [math]l^\star[/math], [math]p^\star[/math] - их дуальное отображение.
  2. [math]p[/math] лежит "над" [math]l[/math] [math]\Leftrightarrow[/math] [math]l^\star[/math] лежит "над" [math]p^\star[/math]


Важно 2:

  • [math]p^\star[/math] - точка в двойственном пространстве, [math]p[/math] - линия в исходном,
  • [math]l^\star[/math] - прямая в двойственном пространстве, [math]l[/math] - точка в исходном,
  • Значок [math]*[/math] означает, что элемент из двойственного пространства.

Рассмотрим множество точек([math]P^\star[/math]) в двойственном пространстве и рассмотрим верхнюю часть выпуклой оболочки, построенной на этих точках. Обозначим её за [math]\mathcal{UH}[/math](Upper hull). Далее мы будем работать только с прямыми(в исходном пространстве), у которых вектор нормали направлен вниз, т.е они образовывают верхнюю цепочку. По свойству выпуклой оболочки, любое ребро из цепи [math]\mathcal{UH}[/math] содержит "ниже" себя все точки множества [math]P^\star[/math], а так же эта цепь соединяет самую правую точку с самой левой.

Рассмотрим какую-то точку [math]p^\star \in P^\star[/math] и заметим, что она будет принадлежать цепи [math]\mathcal{UH}[/math] [math]\Leftrightarrow[/math] [math]\exists[/math] прямая [math]l^\star [/math] : [math]p^\star \in l^\star[/math] и все точки из [math]P^\star[/math] лежат ниже [math]l^\star[/math] (сейчаc мы жили в двойственном пространстве). В обычном пространстве данный факт эквивалентен следующему:

  • Дуальное отображение точки [math]p^\star[/math] в базовое пространство — прямая [math]p[/math], которая по первому свойству содержит точку [math]l[/math](в базовом пространстве прямая [math]p^\star[/math] перешла в точку [math]p[/math]).
  • Так как прямая [math]l^\star[/math] лежит выше всех точек, то теперь каждая прямая из [math]P[/math] лежит выше точки [math]l[/math] (по свойству 2).

Итого: у нас есть точка [math]l[/math] на прямой [math]p[/math], лежащая ниже всех остальных прямых из [math]P[/math].

Посмотрим на планарный граф множества(рис.2) прямых. Из факта выше, мы можем понять, что [math]p[/math] внесла ребро в самый нижний фейс(именно тот, который задаёт часть пересечения полуплоскостей). Обозначим цепочку данного фейса, как [math]\mathcal{LE}[/math]. Математически данную цепочку мы можем описать, как минимум из всех линейных функция (заданные прямыми) в [math]P[/math]. Так же [math]X[/math] компонента узлов этой цепочки монотонно возрастает.

Вернемся к [math]\mathcal{UH}[/math] и заметим, что при обходе цепи, координата [math]X[/math] точек растет. Если же мы будет обходить цепочку из [math]P[/math], образующую пересечение полуплоскостей, мы заметим, что наклон прямых уменьшается. Учитывая этот факт, и то что наклон линии из [math]\mathcal{LE}[/math] совпадет с [math]X[/math] координатой точки (вспоминаем отображение и применяем производную), можно сделать вывод, что обход слева направо точек из цепи [math]\mathcal{UH}[/math], совпадает с обходом точек из [math]\mathcal{LE}[/math] справа налево.

(Обе линии монотоны, одна возрастает, другая убывает. Количество точек в массиве одинаковое, при это каждая точка из [math]\mathcal{UH}[/math] внесла вклад в [math]\mathcal{LE}[/math])

Напоследок, cоседние точки [math]p^\star[/math] и [math]q^\star[/math] из [math]P^\star[/math] образуют какое-то или принадлежат какому-то ребру [math]\mathcal{UH}[/math] [math]\Leftrightarrow[/math] все точки из [math]P^\star[/math] лежат "ниже" линии, построенной на точках [math]p^\star[/math] и [math]q^\star[/math]. В исходном пространстве это означает: все прямые из пространства [math]P[/math] за исключением прямых [math]p[/math] и [math]q[/math] лежат над пересечением [math]p[/math] и [math]q[/math]. Это достаточное условие, что пересечение [math]p[/math] и [math]q[/math] [math]\in[/math] [math]\mathcal{LE}[/math].

Таким образом мы построили верхнее пересечение полуплоскостей. Аналогичным образом строится нижнее, затем мы пересекаем полученные две цепочки.
[math]\triangleleft[/math]

Что же делать с вертикальными линиями?

  1. Найдем все вертикальным прямые за [math]O(N)[/math]. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.
  2. Перейдем в однородное двойственное пространство.

Источники