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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Вставка точки: подправлены О-шки)
 
(не показаны 4 промежуточные версии 3 участников)
Строка 1: Строка 1:
Пусть дано множество точек <tex>S</tex>, изначально пустое, и последовательность точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.
+
Пусть дано множество точек <tex>S</tex>, изначально пустое, и набор точек <tex>\{p_i\}^n_{i = 1}</tex>, которые последовательно добавляются или удаляются из <tex>S</tex> (естественно, точка может быть удалена, если она уже принадлежит <tex>S</tex>). Требуется динамически поддерживать выпуклую оболочку <tex>S</tex>.
  
 
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
 
В статье описан алгоритм, требующий <tex>O(\log^2{n})</tex> времени на добавление/удаление точки.
Строка 34: Строка 34:
 
== Объединение двух выпуклых оболочек ==
 
== Объединение двух выпуклых оболочек ==
  
Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями бинарного поиска для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> . В зависимости от взаимного расположения выпуклых оболочек и секущей имеем 9 случаев (a-i). Для случаев (a-h) на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.
+
Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями [[Целочисленный двоичный поиск|бинарного поиска]] для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <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
 
{|border="0" cellpadding="5" width=30% align=center
Строка 57: Строка 89:
 
|}
 
|}
  
Рассмотрим подробно случай 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>. Случай, когда <tex>s</tex> лежит выше <tex>m</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).
  
 
{|border="0" cellpadding="5" width=30% align=center
 
{|border="0" cellpadding="5" width=30% align=center
Строка 68: Строка 100:
  
 
== Объединение левой и правой выпуклой оболочки ==
 
== Объединение левой и правой выпуклой оболочки ==
 +
Выписываем в порядке обхода вершины из левой выпуклой оболочки, затем выписываем с конца вершины из правой выпуклой оболочки. У них может оказаться от одной до двух общих вершин на концах (две в случае горизонтального ребра снизу/сверху), эта проблема решается путем извлечения "совпадающих" точек в момент обратного обхода правой выпуклой оболочки.
  
 
== Операции ==
 
== Операции ==
Строка 111: Строка 144:
 
=== Вставка точки ===
 
=== Вставка точки ===
  
Вставим точку в дерево, как в обычное сбалансированное дерево поиска. Из-за балансировки мосты в <tex>O(\log{n})</tex> вершинах дерева могут оказаться неактуальными, поэтому, возвращаясь по пути вверх до корня, будем пересчитывать мосты в таких вершинах методом, описанным выше, пользуясь тем, что всё поддерево рассматриваемой вершины уже содержит корректную информацию. Каждый пересчет моста требует <tex>O(\log{n})</tex> времени, откуда итоговая асимптотика вставки: <tex>O(\log^2{n})</tex>.
+
Вставим точку в дерево, как в обычное сбалансированное дерево поиска. После этого необходимо пересчитать мосты для некоторых вершин дерева. В вершине необходимо пересчитать мост, либо если в его поддерево была вставлена вершина, либо если при балансировке в повороте эта вершина была задействована (таких вершин <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>.
  
 
=== Удаление точки ===
 
=== Удаление точки ===

Текущая версия на 20:01, 26 мая 2015

Пусть дано множество точек [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" (и тут тоже)