Изменения

point p // если вершина лист, то точка, хранящаяся в этом листе,

// иначе наименьшая точка в поддереве с корнем в данной вершине

Теперь, когда отсортированные точки хранятся в структуре, поддерживающей эффективный поиск, мы можем воспользоватся идеями бинарного поиска для нахождения моста. Для этого необходим критерий спуска, по которому мы будем определять подотрезок, до которого нужно сузить задачу, имея точки <tex>p</tex> и <tex>q</tex>, определяющие секущую к выпуклым оболочкам множеств <tex>A</tex> и <tex>C</tex> . В зависимости от взаимного расположения выпуклых оболочек и секущей имеем 9 случаев (a-i). Для случаев (a-h) на картинках красным показано, какие части выпуклых оболочек могут быть отброшены. Случай же i немного сложнее.

Рассмотрим подробно случай i.

Итак, на каждом шаге, мы или нашли ответ, или уменьшили размер <tex>A</tex> и/или <tex>C</tex> в два раза, следовательно нахождение моста работает за <tex>O(\log{n})</tex>.