Изменения

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>  <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>

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

 '''Важно 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>lp^\star</tex> в базовое пространство {{---}} прямая <tex>lp</tex>, которая по ''первому свойству'' содержит точку <tex>pl</tex>(в базовом пространстве прямая <tex>p^\star</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>O(N)</tex>. Возьмем самую правую, у которой нормаль смотрит вправо, и самую левую, у которых нормаль смотрит влево. Построим верхнюю цепь и нижнюю цепь без всех вертикальных прямых, затем пересечем верхнюю цепь, нижнюю цепь, самую правую и самую левую вертикальную прямую.# Перейдем в однородное двойственное пространство|двойственного простраства]].'''