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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
 
<includeonly>[[Категория: В разработке]]</includeonly>
 
<includeonly>[[Категория: В разработке]]</includeonly>
  
Пусть дано изначально пустое множество <tex>S</tex> и последовательность точек <tex>\{s_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> времени на добавление/удаление точки.
 +
 +
== Левая и правая выпуклые оболочки ==
 +
 +
Определим левую (правую) выпуклую оболочку множества точек <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</tex>, как выпуклую оболочку множества <tex>P \cup \{\infty_-\} </tex> <tex>(P \cup \{\infty_+\})</tex>, где <tex>\infty_- = (0, -\infty), \infty_+ = (0, +\infty)</tex>. Тогда задачу можно свести к поддержанию отдельно верхней и нижней выпуклых оболочек. Далее будем рассматривать только динамическое поддержание верхней оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой).
 
  
 
Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_x < q_x \lor p_x = q_x \land p_y < q_y</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).  
 
Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_x < q_x \lor p_x = q_x \land p_y < q_y</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).  

Версия 21:47, 28 марта 2014

Эта статья находится в разработке!


Пусть дано множество точек [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]. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек. Далее будем рассматривать только динамическое поддержание левой оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой).

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

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

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

Операции

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

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

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

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

Источники

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