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

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

Пусть дано изначально пустое множество [math]S[/math] и последовательность точек [math]\{s_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_- = (0, -\infty), \infty_+ = (0, +\infty)[/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" (и тут тоже)