Изменения

Как мы узнали ранееописано выше, в худшем случае алгоритм работает за <tex>O\left(n^2\right)</tex>. Теперь внесем Можно внести дополнения, которые позволят получить нам <tex>O\left(n\log n\right)</tex> в худшем случае. Ускорение основывается на уменьшении времени поиска наиболее удаленной вершины. Мы можем это Это можно осуществить благодаря идее о том, что наиболее удаленная вершина лежит на выпуклой оболочке полигональной цепи.

В начале построим выпуклую оболочку алгоритмом Для построения выпуклой оболочки используется алгоритм Мелкмана (Melkman) за <tex>O\left(n\right)</tex>, затем используя бинарный поиск найдем искомую вершину который работает для двумерной полигональной цепи без самопересечений за <tex>O\left(\log n\right)</tex>. Затем, если потребуется, мы разбиваем выпуклую оболочку в найденной точке и опять запускаем двоичный поиск и так далее.Благодаря алгоритму Мелкмана разбиение мы сможем повести за <tex>O\left(\log n\right)</tex>, так как этот алгоритм в процессе построения строит не только искомую выпуклую оболочку, но и строя все промежуточныевыпуклые оболочки, нам остается только сохранить ихкоторые пригодятся в дальнейшем.

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

К сожалению, у данного метода есть несколько недостатковпо сравнению с оригинальным алгоритмом, некоторые из которых уже были упомянуты: