Изменения
→Вставка точки: подправлены О-шки
В статье описан алгоритм, требующий <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>. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем Будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате.
{|border="0" cellpadding="5" width=30% align=center
node parent, left, right
boolean leaf // true, если лист, иначе false
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_aCase_d.png|thumb|300px320px|center|ad. Касательная найденаПо аналогии со случаем b]]|[[Файл: Case_bCase_e.png|thumb|300px320px|center|be. Может быть отброшена часть C после q, а также часть A перед pПо аналогии со случаем c]]|[[Файл: Case_cCase_f.png|thumb|300px320px|center|cf. Может быть отброшена часть C перед после q, а также часть A перед p]]
|
|}
{|border="0" cellpadding="5" width=30% align=center
|[[Файл: Case_dCase_g.png|thumb|300px320px|center|dg. По аналогии со случаем bТолько часть C после q может быть отброшена]]|[[Файл: Case_eCase_h.png|thumb|300px320px|center|eh. По аналогии со случаем cg]]|[[Файл: Case_fCase_i.png|thumb|300px320px|center|fi. Может быть отброшена часть C после qВ этом случае нельзя сразу сказать, а также часть какие части A перед pи 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_gCase_i1.png|thumb|300px320px|center|gi1. Только часть C после q может быть отброшенаТочка пересечения лежит ниже прямой m]]|[[Файл: Case_hCase_i2.png|thumb|300px320px|center|hi2. По аналогии со случаем h]]|[[Файл: Case_i.png|thumb|300px|center|i. В этом случае нельзя сразу сказать, какие части A и C могут быть отброшены. Случай дробится на дваТочка пересечения лежит выше прямой m]]
|
|}
== Операции ==
=== Получение выпуклой оболочки ===
Научимся восстанавливать выпуклую оболочку по дереву, описанному выше. Для этого рассмотрим более общую задачу: для данной вершины дерева <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>.
=== Удаление точки ===