Изменения

Пусть дано множество точек <div styletex>S</tex>, изначально пустое, и набор точек <tex>\{p_i\}^n_{i ="background-color: #ABCDEF; font-size: 16px; font-weight: bold; color: #000000; text-align: center; padding: 4px; border-style: solid; border-width: 1px;"1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>Эта статья находится в разработке!S</divtex>). Требуется динамически поддерживать выпуклую оболочку <includeonlytex>[[Категория: В разработке]]S</includeonlytex>.

Пусть дано изначально пустое множество В статье описан алгоритм, требующий <tex>SO(\log^2{n})</tex> времени на добавление/удаление точки. == Левая и последовательность правая выпуклые оболочки == Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\}</tex> <tex>(P \cup \{s_i\infty_-\}^n_)</tex>, где <tex>\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате. {i |border= 1"0" cellpadding="5" width=30% align=center|[[Файл:Lc_rc.png|400px|thumb|center|Левая и правая выпуклые оболочки некоторого множества точек]]|[[Файл:Bridge_hull.png|400px|thumb|center|Мост B между двумя выпуклыми оболочками, разделенными горизонтальной прямой]]||} Пусть множество точек <tex>P</tex>, которые последовательно добавляются или удаляются из разбито горизонтальной прямой на два множества <tex>A</tex> и <tex>C</tex>. Рассмотрим выпуклые оболочки <tex>A</tex> и <tex>SC</tex> . Будем называть мостом (естественноbridge) отрезок общей касательной к этим оболочкам, точка может быть удаленазаключённый между точками касания. Тогда выпуклая оболочка ко всему множеству <tex>P</tex> естественным образом получается объединением частей оболочек <tex>A</tex> и <tex>C</tex>, если она уже принадлежит и моста <tex>B</tex>. Основная идея алгоритма заключается в эффективном (за <tex>SO(\log{n})</tex>)отыскании моста, соединяющего две такие оболочки. Требуется на каждой итерации поддерживать выпуклую оболочку  == Структура данных == Будем хранить отсортированные лексикографически (<tex>Sp < q \Leftrightarrow p_y < q_y \lor p_y = q_y \land p_x < q_x</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]).Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, мост между выпуклыми оболочками точек левого и правого поддеревьев данной вершины. Формально вершина дерева описывается так:  '''struct''' bridge point left point right  '''struct''' node node parent, left, right boolean leaf // true, если лист, иначе false bridge b // поле валидно для внутренней вершины point p // если вершина лист, то точка, хранящаяся в этом листе, // иначе наименьшая точка в поддереве с корнем в данной вершине

== Объединение двух выпуклых оболочек == Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями [[Целочисленный двоичный поиск|бинарного поиска]] для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> .  Рассмотрим дополнительно 4 точки: <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> {{---}} наибольшая. Тогда в зависимости от взаимного расположения вектора <tex>\overrightarrow{qp}</tex> и точек <tex>p^{+}</tex>, <tex>p^{-}</tex>, <tex>q^{+}</tex>, <tex>q^{-}</tex> можно определить, какой из 9 случаев рассматривать, а именно: :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> Для случаев a-h на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее. {|border="0" cellpadding="5" width=30% align=center|[[Файл: Case_a.png|thumb|320px|center|a. Касательная найдена]]|[[Файл: Case_b.png|thumb|320px|center|b. Может быть отброшена часть C после q, а также часть A перед p]]|[[Файл: Case_c.png|thumb|320px|center|c. Может быть отброшена часть C перед q, а также часть A перед p]]||} {|border="0" cellpadding="5" width=30% align=center|[[Файл: Case_d.png|thumb|320px|center|d. По аналогии со случаем b]]|[[Файл: Case_e.png|thumb|320px|center|e. По аналогии со случаем c]]|[[Файл: Case_f.png|thumb|320px|center|f. Может быть отброшена часть C после q, а также часть A перед p]]||} {|border="0" cellpadding="5" width=30% align=center|[[Файл: Case_g.png|thumb|320px|center|g. Только часть C после q может быть отброшена]]|[[Файл: Case_h.png|thumb|320px|center|h. По аналогии со случаем g]]|[[Файл: Case_i.png|thumb|320px|center|i. В статье описан алгоритмэтом случае нельзя сразу сказать, какие части A и C могут быть отброшены. Случай дробится на два]]||} Рассмотрим подробно случай 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). {|border="0" cellpadding="5" width=30% align=center|[[Файл: Case_i1.png|thumb|320px|center|i1. Точка пересечения лежит ниже прямой m]]|[[Файл: Case_i2.png|thumb|320px|center|i2. Точка пересечения лежит выше прямой m]]||} Итак, требующий на каждом шаге, мы или нашли ответ, или уменьшили размер <tex>A</tex> и/или <tex>C</tex> в два раза, следовательно нахождение моста работает за <tex>O(\log^2{n})</tex> времени . == Объединение левой и правой выпуклой оболочки ==Выписываем в порядке обхода вершины из левой выпуклой оболочки, затем выписываем с конца вершины из правой выпуклой оболочки. У них может оказаться от одной до двух общих вершин на добавлениеконцах (две в случае горизонтального ребра снизу/сверху), эта проблема решается путем извлечения "совпадающих" точек в момент обратного обхода правой выпуклой оболочки. == Операции == === Получение выпуклой оболочки === Научимся восстанавливать выпуклую оболочку по дереву, описанному выше. Для этого рассмотрим более общую задачу: для данной вершины дерева <tex>v</удаление tex> и отрезка <tex>[l, r]</tex> найти часть выпуклой оболочки, состоящей из точек поддерева с корнем в <tex>v</tex>, ординаты которых лежат в этом отрезке. Это можно сделать следующим обходом:  get_hull(answer, v, l, r) '''if''' (v.leaf) '''return''' a = v.bridge.left.y b = v.bridge.right.y '''if''' (l < a) get_hull(answer, v.left, l, min(a, r)) '''if''' (l <= a '''and''' b <= r) '''if''' (answer.empty()) answer = answer ++ v.bridge.left answer = answer ++ v.bridge.right '''if''' (b < r) get_hull(answer, v.right, max(l, b), r) Левый конец моста добавляется только если ответ пустой, иначе он уже был добавлен как правый конец другого моста. Чтобы получить выпуклую оболочку нужно вызвать get_hull([], root, <tex>-\infty</tex>, <tex>+\infty</tex>). === Принадлежность точкивыпуклой оболочке === По аналогии с предыдущим пунктом, сведем запрос к более общему запросу: для данной вершины дерева <tex>v</tex> и отрезка <tex>[l, r]</tex> проверить, принадлежит ли точка <tex>p</tex> части выпуклой оболочки, состоящей из точек поддерева с корнем в <tex>v</tex>, ординаты которых лежат в этом отрезке.Тогда принадлежность точки проверяется вызовом in_hull(p, root, <tex>-\infty</tex>, <tex>+\infty</tex>)  in_hull(p, v, l, r) '''if''' (v.leaf) '''return''' '''false''' a = v.bridge.left.y b = v.bridge.right.y '''if''' (l <= a and b <= r) '''if''' (v.bridge.left == p '''or''' v.bridge.right == p) '''return''' '''true''' '''if''' (l < a '''and''' p.y < a) '''return''' in_hull(p, v.left, l, min(a, r)) '''if''' (b < r '''and''' b < p.y) '''return''' in_hull(p, v.right, max(l, b), r) '''return''' '''false''' === Вставка точки ===

== Левые и правые выпуклые оболочкиВставим точку в дерево, как в обычное сбалансированное дерево поиска. После этого необходимо пересчитать мосты для некоторых вершин дерева. В вершине необходимо пересчитать мост, либо если в его поддерево была вставлена вершина, либо если при балансировке в повороте эта вершина была задействована (таких вершин <tex>O(\log{n})</tex>. Мосты в таких вершинах будем пересчитывать при подъеме по дереву после вставки вершины. Глубина дерева <tex>O(\log{n})</tex>, значит в процессе подъема будут пересчитаны мосты у <tex>O(\log{n})</tex> вершин. Каждый пересчет моста требует <tex>O(\log{n})</tex> времени, откуда итоговая асимптотика вставки: <tex>O(\log^2{n})</tex>. Эффективная конкатенация двух левых оболочек ==

Определим левую (правую) выпуклую оболочку множества точек <tex>P</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_+\} </tex> <tex>(P \cup \{\infty_-\})</tex>, где <tex>\infty_L = (-\infty, 0), \infty_R = (+\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек.= Удаление точки ===