Динамическая выпуклая оболочка (достаточно 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_L = (-\infty, 0), \infty_R = (+\infty, 0)[/math]. Тогда задачу можно свести к поддержанию отдельно левой и правой выпуклых оболочек.