Асимптотика : аналогично обычному алгоритму построения выпуклой оболочки, каждая прямая ровно <math>1</math> раз добавится в стек и максимум <math>1</math> раз удалится. Значит время работы перестройки выпуклой оболочки займет <tex>O(n)</tex> суммарно.
Корректность : достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю.
[[Файл:picture2convexhull.png]]
[[Файл:picture3convexhull.png]]
Доказательство : {{Теорема|id=th1239. |statement=Алгоритм построения нижней огибающей множества прямых корректен.|proof=Достаточно показать, что последнюю прямую нужно удалить из множества т.и т.т., когда она наша новая прямая пересекает ее в точке с координатой по оси X, меньшей, чем последняя - предпоследнюю. Пусть <tex>Y(x) = Kx + B</tex> - уравнение новой прямой, <tex>y[i](x) = K[i]x + B[i]</tex> - уравнения прямых множества. Тогда т.к. <tex>K < K[sz]</tex>, то при <tex>x \in [- \infty; xR] : y[sz](x) <= Y(x)</tex>, а т.к. <tex> K[sz] < K[sz - 1]</tex>, то при <tex>x \in [xL; + \infty] : y[sz - 1](x) \geqslant y[sz](x)</tex>. Если <tex>xL < xR</tex>, то при <tex>x \in [xL; xR] : y[sz - 1] \geqslant y[sz](x) и Y(x) \geqslant y[sz](x)</tex>, т.е. на отрезке <tex>[xL; xR]</tex> прямая номер sz лежит ниже остальных и её нужно оставить в множестве. Если же <tex>xL > xR</tex>, то она ниже всех на отрезке <tex>[xL; xR] = \varnothing </tex>, т.е. её можно удалить из множества}}
==Детали реализации:==
B[i] = dp[i] <font color=green>// наши переобозначения переменных </font >
x = -<tex>\infty</tex>
'''while''' (''true'')
j = st[sz]
x = divide(B[j] - B[i], K[i] - K[j]) <font color=green>// x-координата пересечения с последней прямой оболочки, округленное в нужную сторону (*) </font >
