Изменения

Пусть дано множество точек <tex>S</tex>, изначально пустое, и последовательность набор точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.

Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями [[Целочисленный двоичный поиск|бинарного поиска ]] для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> .

<tex>p^{+}</tex> {{--- }} следующая за <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{+} > p_{y}</tex> и ордината <tex>p_{y}</tex> {{--- }} наименьшая.

<tex>p^{-}</tex> {{--- }} предыдущая <tex>p</tex> точка выпуклой оболочки множества <tex>A</tex> в отсортированном порядке, то есть <tex>p_{y}^{-} < p_{y}</tex> и ордината <tex>p_{y}</tex> {{--- }} наибольшая.

<tex>q^{+}</tex> {{--- }} следующая за <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{+} > q_{y}</tex> и ордината <tex>q_{y}</tex> {{--- }} наименьшая.

<tex>q^{-}</tex> {{--- }} предыдущая <tex>q</tex> точка выпуклой оболочки множества <tex>C</tex> в отсортированном порядке, то есть <tex>q_{y}^{-} < q_{y}</tex> и ордината <tex>q_{y}</tex> {{--- }} наибольшая.

:a) Все точки <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> расположены справа от вектора <tex>\overrightarrow{qp}</tex> (т.е. образуют с ним правый точка <tex>t</tex> находится слева (справа) от вектора <tex>\overrightarrow{qp}</tex>, если [[Предикат "левый поворот"|предикат "левый поворот"]] для точек <tex>q</tex>, <tex>p</tex>, <tex>t</tex> положительный (отрицательный)) {{- --}} найден мост.

:b) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex> {{--- }} справа, <tex>q^{-}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

:c) <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{-}</tex> {{--- }} справа, <tex>q^{+}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

:d) Как в случае b, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{+}</tex>

:e) Как в случае c, только слева от <tex>\overrightarrow{qp}</tex> находится точка <tex>p^{-}</tex>

:f) <tex>p^{-}</tex>, <tex>q^{+}</tex> {{--- }} справа, <tex>p^{+}</tex>, <tex>q^{-}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

:g) <tex>p^{+}</tex>, <tex>q^{+}</tex> {{--- }} справа, <tex>p^{-}</tex>, <tex>q^{-}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

:h) <tex>p^{-}</tex>, <tex>q^{-}</tex> {{--- }} справа, <tex>p^{+}</tex>, <tex>q^{+}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

:i) <tex>p^{+}</tex>, <tex>q^{-}</tex> {{--- }} справа, <tex>p^{-}</tex>, <tex>q^{+}</tex> {{--- }} слева от <tex>\overrightarrow{qp}</tex>

Рассмотрим подробно случай i. Пусть <tex>m</tex> {{---}} прямая, разбивающая <tex>P</tex> на <tex>A</tex> и <tex>C</tex>. Пусть также <tex>l_p</tex> и <tex>l_q</tex> {{---}} касательные к выпуклым оболочкам в точках <tex>p</tex> и <tex>q</tex> соответственно. Если <tex>s</tex> {{---}} точка пересечения <tex>l_p</tex> и <tex>l_q</tex> лежит ниже прямой <tex>m</tex>, то точка пересечения моста и выпуклой оболочки <tex>A</tex> может лежать в треугольнике, образованном прямыми <tex>l_p</tex>, <tex>l</tex> и <tex>m</tex>, или выше <tex>p</tex>. Тогда можем удалить часть <tex>C</tex> ниже <tex>q</tex>(см. рис. i1). Случай, когда <tex>s</tex> лежит выше <tex>m</tex>, аналогичен (см. рис.i2).