74
правки
Изменения
Нет описания правки
<includeonly>[[Категория: В разработке]]</includeonly>
Пусть дано изначально пустое множество точек <tex>S</tex> , изначально пустое, и последовательность точек <tex>\{s_ip_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется на каждой итерации динамически поддерживать выпуклую оболочку <tex>S</tex>.
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
== Левая и правая выпуклые оболочки ==
Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\}</tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой).
[[Файл:Lc_rc.png|400px|thumb|center|Левая и правая выпуклые оболочки некоторого множества точек]]
== Структура данных ==
Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_x < q_x \lor p_x = q_x \land p_y < q_y</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).
