Динамическая выпуклая оболочка (достаточно log^2 на добавление/удаление)

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

В статье описан алгоритм, требующий [math]O(\log^2{n})[/math] времени на добавление/удаление точки.

Левая и правая выпуклые оболочки

Определим левую (правую) выпуклую оболочку множества точек [math]P[/math], как выпуклую оболочку множества [math]P \cup \{\infty_+\}[/math] [math](P \cup \{\infty_-\})[/math], где [math]\infty_- = (-\infty, 0), \infty_+ = (+\infty, 0)[/math]. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Заметим также, что точки вдоль выпуклой оболочки отсортированы по ординате.

Левая и правая выпуклые оболочки некоторого множества точек

Мост B между двумя выпуклыми оболочками, разделенными горизонтальной прямой

Пусть множество точек [math]P[/math] разбито горизонтальной прямой на два множества [math]A[/math] и [math]C[/math]. Рассмотрим выпуклые оболочки [math]A[/math] и [math]C[/math]. Будем называть мостом (bridge) отрезок общей касательной к этим оболочкам, заключённый между точками касания. Тогда выпуклая оболочка ко всему множеству [math]P[/math] естественным образом получается объединением частей оболочек [math]A[/math] и [math]C[/math], и моста [math]B[/math].

Основная идея алгоритма заключается в эффективном (за [math]O(\log{n})[/math]) отыскании моста, соединяющего две такие оболочки.

Структура данных

Будем хранить отсортированные лексикографически ([math]p \lt q \Leftrightarrow p_y \lt q_y \lor p_y = q_y \land p_x \lt q_x[/math]) точки в листьях сбалансированного бинарного дерева поиска (например, красно-черного или AVL). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, мост между выпуклыми оболочками точек левого и правого поддеревьев данной вершины. Формально вершина дерева описывается так:

struct bridge
   point left
   point right

struct node
   node    parent, left, right
   boolean leaf  // true, если лист, иначе false
   bridge  b     // поле валидно для внутренней вершины
   point   p     // если вершина лист, то точка, хранящаяся в этом листе,
                 // иначе наименьшая точка в поддереве с корнем в данной вершине

Объединение двух выпуклых оболочек

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

Рассмотрим дополнительно 4 точки:

[math]p^{+}[/math] — следующая за [math]p[/math] точка выпуклой оболочки множества [math]A[/math] в отсортированном порядке, то есть [math]p_{y}^{+} \gt p_{y}[/math] и ордината [math]p_{y}[/math] — наименьшая.

[math]p^{-}[/math] — предыдущая [math]p[/math] точка выпуклой оболочки множества [math]A[/math] в отсортированном порядке, то есть [math]p_{y}^{-} \lt p_{y}[/math] и ордината [math]p_{y}[/math] — наибольшая.

[math]q^{+}[/math] — следующая за [math]q[/math] точка выпуклой оболочки множества [math]C[/math] в отсортированном порядке, то есть [math]q_{y}^{+} \gt q_{y}[/math] и ордината [math]q_{y}[/math] — наименьшая.

[math]q^{-}[/math] — предыдущая [math]q[/math] точка выпуклой оболочки множества [math]C[/math] в отсортированном порядке, то есть [math]q_{y}^{-} \lt q_{y}[/math] и ордината [math]q_{y}[/math] — наибольшая.

Тогда в зависимости от взаимного расположения вектора [math]\overrightarrow{qp}[/math] и точек [math]p^{+}[/math], [math]p^{-}[/math], [math]q^{+}[/math], [math]q^{-}[/math] можно определить, какой из 9 случаев рассматривать, а именно:

a) Все точки [math]p^{+}[/math], [math]p^{-}[/math], [math]q^{+}[/math], [math]q^{-}[/math] расположены справа от вектора [math]\overrightarrow{qp}[/math] (точка [math]t[/math] находится слева (справа) от вектора [math]\overrightarrow{qp}[/math], если предикат "левый поворот" для точек [math]q[/math], [math]p[/math], [math]t[/math] положительный (отрицательный)) — найден мост.

b) [math]p^{+}[/math], [math]p^{-}[/math], [math]q^{+}[/math] — справа, [math]q^{-}[/math] — слева от [math]\overrightarrow{qp}[/math]

c) [math]p^{+}[/math], [math]p^{-}[/math], [math]q^{-}[/math] — справа, [math]q^{+}[/math] — слева от [math]\overrightarrow{qp}[/math]

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

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

f) [math]p^{-}[/math], [math]q^{+}[/math] — справа, [math]p^{+}[/math], [math]q^{-}[/math] — слева от [math]\overrightarrow{qp}[/math]

g) [math]p^{+}[/math], [math]q^{+}[/math] — справа, [math]p^{-}[/math], [math]q^{-}[/math] — слева от [math]\overrightarrow{qp}[/math]

h) [math]p^{-}[/math], [math]q^{-}[/math] — справа, [math]p^{+}[/math], [math]q^{+}[/math] — слева от [math]\overrightarrow{qp}[/math]

i) [math]p^{+}[/math], [math]q^{-}[/math] — справа, [math]p^{-}[/math], [math]q^{+}[/math] — слева от [math]\overrightarrow{qp}[/math]

Для случаев a-h на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.

a. Касательная найдена

b. Может быть отброшена часть C после q, а также часть A перед p

c. Может быть отброшена часть C перед q, а также часть A перед p

d. По аналогии со случаем b

e. По аналогии со случаем c

f. Может быть отброшена часть C после q, а также часть A перед p

g. Только часть C после q может быть отброшена

h. По аналогии со случаем g

i. В этом случае нельзя сразу сказать, какие части A и C могут быть отброшены. Случай дробится на два

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

i1. Точка пересечения лежит ниже прямой m

i2. Точка пересечения лежит выше прямой m

Итак, на каждом шаге, мы или нашли ответ, или уменьшили размер [math]A[/math] и/или [math]C[/math] в два раза, следовательно нахождение моста работает за [math]O(\log{n})[/math].

Объединение левой и правой выпуклой оболочки

Выписываем в порядке обхода вершины из левой выпуклой оболочки, затем выписываем с конца вершины из правой выпуклой оболочки. У них может оказаться от одной до двух общих вершин на концах (две в случае горизонтального ребра снизу/сверху), эта проблема решается путем извлечения "совпадающих" точек в момент обратного обхода правой выпуклой оболочки.

Операции

Получение выпуклой оболочки

Научимся восстанавливать выпуклую оболочку по дереву, описанному выше. Для этого рассмотрим более общую задачу: для данной вершины дерева [math]v[/math] и отрезка [math][l, r][/math] найти часть выпуклой оболочки, состоящей из точек поддерева с корнем в [math]v[/math], ординаты которых лежат в этом отрезке. Это можно сделать следующим обходом:

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, [math]-\infty[/math], [math]+\infty[/math]).

Принадлежность точки выпуклой оболочке

По аналогии с предыдущим пунктом, сведем запрос к более общему запросу: для данной вершины дерева [math]v[/math] и отрезка [math][l, r][/math] проверить, принадлежит ли точка [math]p[/math] части выпуклой оболочки, состоящей из точек поддерева с корнем в [math]v[/math], ординаты которых лежат в этом отрезке. Тогда принадлежность точки проверяется вызовом in_hull(p, root, [math]-\infty[/math], [math]+\infty[/math])

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

Вставка точки

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

Удаление точки

Удаление точки производится по аналогии с вставкой: сначала мы удалим точку из сбалансированного дерева поиска, а затем пересчитаем мосты, хранящиеся в вершинах, которые затронула балансировка. Очевидно, что удаление, как и вставка, работает за [math]O(\log^2{n})[/math].

Источники

• Реализация Антона Ковшарова
• Ф. Препарата, М. Шеймос. Вычислительная геометрия (1989). стр. 151 (тут описан более сложный алгоритм с двухуровневой структурой данных, но с такой же асимптотикой)
• Overmars, M. H.; van Leeuwen, J. (1981), "Maintenance of configurations in the plane" (и тут тоже)