Изменения

Перейти к: навигация, поиск
Нет описания правки
В статье описан алгоритм, требующий <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, 0), \infty_R infty_+ = (0, +\infty, 0)</tex>. Тогда задачу можно свести к поддержанию отдельно левой верхней и правой нижней выпуклых оболочек.Далее будем рассматривать только динамическое поддержание верхней оболочки (далее, для краткости, будем называть её просто выпуклой оболочкой). Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_x < q_x \lor p_x = q_x \land p_y < q_y</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).  == Операции == === Получение выпуклой оболочки === === Принадлежность точки выпуклой оболочке === === Вставка точки === === Удаление точки ===
== Алгоритм ==
== Источники ==
* [https://github.com/antonkov/cg/blob/master/include/cg/convex_hull/dynamic_hull.h Реализация Антона Ковшарова]
* Ф. Препарата, М. Шеймос. Вычислительная геометрия (1989). стр. 151 (тут описан более сложный алгоритм с двухуровневой структурой данных, но с такой же асимптотикой)
* Overmars, M. H.; van Leeuwen, J. (1981), "Maintenance of configurations in the plane" (и тут тоже)
 
[[Категория: Вычислительная геометрия]]
Анонимный участник

Навигация