node parent, left, right
boolean leaf // true, если лист, иначе false
point p bridge b // поле валидно для листавнутренней вершины bridge b point p // поле валидно если вершина лист, то точка, хранящаяся в этом листе, // иначе наименьшая точка в поддереве с корнем в данной вершине Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями бинарного поиска для внутренней вершины нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> . В зависимости от взаимного расположения выпуклых оболочек и секущей имеем 9 случаев (a-i). Для случаев (a-h) на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.
{|border="0" cellpadding="5" width=30% align=center
|
|}
Рассмотрим подробно случай i. Итак, на каждом шаге, мы или нашли ответ, или уменьшили размер <tex>A</tex> и/или <tex>C</tex> в два раза, следовательно нахождение моста работает за <tex>O(\log{n})</tex>.
== Операции ==
