304
правки
Изменения
Нет описания правки
Построив выпуклую оболочку, используется бинарный поиск для нахождения наиболее удаленной вершины за <tex>O(\log n)</tex>. Затем, если потребуется, действия повторятся рекурсивно, как и в оригинальном алгоритме, но заново строить оболочки не имеет смысла, так как промежуточные уже были построены. Использовав их, можно разбить текущую оболочку на две за <tex>O(\log n)</tex>.
В итоге получается , что в худшем случае <tex>O(n)</tex> разбиений за <tex>O(\log n)</tex> и поиск за <tex>O(\log n)</tex> в худшем случае, что дает <tex>O(n\log n)</tex>.
===Замечания===
К сожалению, у данного метода есть несколько недостатков по сравнению с оригинальным алгоритмом, некоторые из которых уже были упомянуты:
