Изменения

*Оба предыдущих условия ложны, то <tex>abs(| \overrightarrow{R_{12}} \times \overrightarrow{R_1}|/|\overrightarrow{R_{12}}|)</tex>, где <tex> \overrightarrow{R_{12}} = (x_2 -x_1, y_2 - y_1)</tex> и <tex> \overrightarrow{R_1} = (x_1 - x_0, y_1 - y_0)</tex>. Это следует из формул для площади параллелограмма через векторное произведение и через произведения основания на высоту

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