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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
м (rollbackEdits.php mass rollback)
 
(не показано 66 промежуточных версий 8 участников)
Строка 1: Строка 1:
−
<div style="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;">Эта статья находится в разработке!</div>
+
[[Файл:samplesHalfspaces.png|400px|thumb|right|Пересечение существует и выпукло, неограниченно или пусто]]
−
<includeonly>[[Категория: В разработке]]</includeonly>
 
  
−
[[Файл:dual.png|400px|thumb|right|типа это одно и то же]]
+
== Предикат трех прямых ==
 +
Задача: есть конечное множество полуплоскостей, найти фигуру их пересечения или сообщить что оно пусто.
  
−
Короче говоря, верхний(нижний) конвекс-халл для множества точек, то же самое, что и нижняя(верхняя) огибающая(англ. lower(upper) envelope) для множества прямых.
+
Для начала заметим, что если пересечение не пусто, то оно выпукло. (Доказательство {{---}} Пересечение выпуклых фигур выпукло, а полуплоскость выпукла)
  
−
Если рассмотреть что ребро <tex> PQ </tex> принадлежит верхнему конвекс-халлу это означает, что все остальные точки лежат снизу. А если ребро <tex> PQ </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> и домножим на определитель.
  
−
Тут бы и закончить конспект, но стоит уточнить, что у пересечения полуплоскостей есть одна небольшая особенность {{---}} оно может быть пусто, тогда как выпуклая оболочка вполне себе всегда определена, и это надо учитывать. И еще. когда мы рассматриваем верхнюю(нижнюю) огибающую, мы рассматриваем все прямые кроме вертикальных. Еще прямые близкие к вертикальным, но имеющие разный наклон (/ и \) are mapped to very different points. Отсюда выходит то, почему конвекс-халл состоит из двух таких разных и одинаковых частей.
+
<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>
 +
= 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>
  
−
Convex Hulls and Half-Space Intersection
+
<tex>
−
In Chapter 8 we have met the concept of duality. The strenth of duality lies in that it allows us to look at a problem from a new perspective, which can lead to more insight in what is really going on. Recall that we denote the line that is the dual of a point p by p ∗ , and the point that is the dual of a line by ∗ . The duality transform is incidence and order preserving: p ∈ if and only if ∗ ∈ p ∗ , and p lies above if and only if ∗ lies above p ∗ . Let’s have a closer look at what convex hulls correspond to in dual space. We will do this for the planar case. Let P be a set of points in the plane. For technical reasons we focus on its upper convex hull, denoted UH(P), which consists of the convex hull edges that have P below their supporting line—see the left side of Figure 11.4. The upper convex hull is a polygonal chain that connects the leftmost point in P to the rightmost one. (We assume for simplicity that no two points have the same x-coordinate)
+
= 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>
 +
}}
  
−
When does a point p ∈ P appear as a vertex of the upper convex hull? That is the case if and only if there is a non-vertical line through p such that all
+
Таким образом, если представить прямую <tex> Ax + By + C = 0 </tex> как точку с однородными координатами <tex> (A, B, C) </tex>, то этот предикат {{---}} всего лишь поворот, а проверка предиката {{---}} проверка очередной точки в [[Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull#Алгоритм Грэхема|обходе Грэхема]] для нахождения выпуклой оболочки.
−
other points of P lie below . In the dual plane this statement translates to the following condition: there is a point ∗ on the line p ∗ ∈ P ∗ such that ∗ lies below all other lines of P ∗ . If we look at the arrangement A(P ∗ ), this means that p ∗ contributes an edge to the unique bottom cell of the arrangement. This cell is the intersection of the half-planes bounded by a line in P ∗ and lying below that line. The boundary of the bottom cell is an x-monotone chain. We can define this chain as the minimum of the linear functions whose graphs are the lines in P ∗ . For this reason, the boundary of the bottom cell in an arrangement is often called the lower envelope of the set of lines. We denote the lower envelope of P ∗ by LE(P ∗ )—see the right hand side of Figure 11.4. The points in P that appear on UH(P) do so in order of increasing x-coordinate. The lines of P ∗ appear on the boundary of the bottom cell in order of decreasing slope. Since the slope of the line p ∗ is equal to the x-coordinate of p, it follows that the left-to-right list of points on UH(P) corresponds exactly to the right-to-left list of edges of LE(P ∗ ). So the upper convex hull of a set of points is essentially the same as the lower envelope of a set of lines.
 
  
−
Let’s do one final check. Two points p and q in P form an upper convex hull edge if and only if all other points in P lie below the line through p and
+
Алгоритм:
−
q. In the dual plane, this means that all lines r ∗ , with r ∈ P \ {p, q}, lie above the intersection point ∗ of p ∗ and q ∗ . This is exactly the condition under which p ∗ ∩ q ∗ is a vertex of LE(P ∗ ). What about the lower convex hull of P and the upper envelope of P ∗ ? (We leave the precise definitions to the reader.) By symmetry, these concepts are dual to each other as well. We now know that the intersection of lower half-planes—half-planes bounded from above by a non-vertical line—can be computed by computing an upper convex hull, and that the intersection of upper half-planes can be computed by computing a lower convex hull. But what if we want to compute the intersection of an arbitrary set H of half-planes? Of course, we can split the set H into a set H + of upper half-planes and a set H − of lower half-planes, compute H + by computing the lower convex hull of H + ∗ and H − by computing the upper convex hull of H − ∗ , and then compute H by intersecting H + and H − . But is this really necessary? If lower envelopes correspond to upper convex
+
* Отсортировать все полуплоскости по углу наклона;
−
hulls, and upper envelopes correspond to lower convex hulls, shouldn’t then the intersection of arbitrary half-planes correspond to full convex hulls? In a
+
* Запустить обход Грэхема для полуплоскостей, смотрящих вниз (с предикатом-определителем);
−
sense, this is true. The problem is that our duality transformation cannot handle vertical lines, and lines that are close to vertical but have opposite slope are mapped to very different points. This explains why the dual of the convex hull consists of two parts that lie rather far apart.
+
* Запустить обход Грэхема для полуплоскостей, смотрящих вверх;
 +
* Пересечь две цепочки.
  
−
It is possible to define a different duality transformation that allows vertical lines. However, to apply this duality to a given set of half-planes, we need a point in the intersection of the half-planes. But that was to be expected. As long as we do not want to leave the Euclidean plane, there cannot be any general duality that turns the intersection of a set of half-planes into a convex hull, because the intersection of half-planes can have one special property: it can be empty. What could that possibly correspond to in the dual? The convex hull of a set of points in Euclidean space is always well defined: there is no such thing as “emptiness.” (This problem is nicely solved if one works in oriented projective space, but this concept is beyond the scope of this book.) Only once you know that the intersection is not empty, and a point in the interior is known, can you define a duality that relates the intersection with a convex hull. We leave it at this for now. The important thing is that—although there are technical complications—convex hulls and intersections of half-planes (or half-spaces in three dimensions) are essentially dual concepts. Hence, an algorithm to compute the intersection of half-planes in the plane (or half-spaces in three dimensions) can be given by dualizing a convex-hull algorithm.
+
От пересечения цепочек напрямую зависит фигура пересечения: неограниченная область получается если одна из цепочек пуста, а ограниченная {{---}} когда обе цепочки не пусты и пересекаются.
 +
 
 +
== Связь пересечения полуплоскостей с выпуклой оболочкой ==
 +
 
 +
{{Лемма
 +
|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>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.
 +
# Перейдем в однородное двойственное пространство.
  
 
== Источники ==
 
== Источники ==
−
* 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 15 page 253-254
+
* 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
 
[[Категория: Вычислительная геометрия]]
 
[[Категория: Вычислительная геометрия]]

Текущая версия на 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. Перейдем в однородное двойственное пространство.

Источники

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Пересечение_полуплоскостей,_связь_с_выпуклыми_оболочками&oldid=84410»