74
правки
Изменения
Нет описания правки
Основная идея алгоритма заключается в эффективном (за <tex>O(\log{n})</tex>) отыскании моста, соединяющего две такие оболочки.
== Структура данных ==
Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_y < q_y \lor p_y = q_y \land p_x < q_x</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, мост между выпуклыми оболочками точек левого и правого поддеревьев данной вершины. Формально вершина дерева описывается так:
'''struct''' bridge
point left
point right
'''struct''' node
node parent, left, right
boolean leaf // true, если лист, иначе false
point p // поле валидно для листа
bridge b // поле валидно для внутренней вершины
{|border="0" cellpadding="5" width=30% align=center
|
|}
== Операции ==
