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

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

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

Будем хранить отсортированные лексикографически ([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" (и тут тоже)