Изменения

Перейти к: навигация, поиск
Нет описания правки
Основная идея алгоритма заключается в эффективном (за <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
|
|}
 == Структура данных == Будем хранить отсортированные лексикографически (<tex>p < q \Leftrightarrow p_x < q_x \lor p_x = q_x \land p_y < q_y</tex>) точки в листьях сбалансированного бинарного дерева поиска (например, [[Красно-черное дерево|красно-черного]] или [[АВЛ-дерево|AVL]]). Во внутренних вершинах будем хранить вспомогательную информацию: во-первых, наименьшую точку в поддереве с корнем в данной вершине; а во-вторых, пару точек, определяющих общую касательную к выпуклым оболочкам точек левого и правого поддеревьев данной вершины (будем называть такую пару точек мостом).
== Операции ==
73
правки

Навигация