Изменения

== Левые и правые выпуклые оболочки. Эффективная конкатенация двух левых оболочек Структура данных ==

Определим левую верхнюю (правуюнижнюю) выпуклую оболочку множества точек <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]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).  == Операции == === Получение выпуклой оболочки === === Принадлежность точки выпуклой оболочке === === Вставка точки === === Удаление точки ===