Изменения

1) # Возьмем точку <tex>p_0</tex> нашего множества с самой маленькой у-координатой (если таких несколько, берем самую правую из них). Добавляем ее в ответ. 2) # На каждом следующем шаге для последнего добавленного <tex>p_i</tex> ищем <tex>p_{i + 1}</tex> среди всех недобавленных точек и <tex>p_0</tex> {{Acronym|с максимальным полярным углом относительно <tex>p_i</tex> (Если углы равны, надо сравнивать по расстоянию)|Считать углы не нужно, можно просто подставить в функцию сравнения предикат поворота}}. Добавляем <tex>p_{i + 1}</tex> в ответ. Если <tex>p_{i + 1} == p_0</tex> , заканчиваем алгоритм.

1)* База. Для трех первых точек утверждение, очевидно, выполняется.

2)* Переход. Пусть для <tex>i-1</tex> точек оболочки совпадают. Докажем, что и для <tex>i</tex> точек они совпадут.

1)# Находим самую левую и самую правую точки множества - <tex>p_0</tex> и <tex>p_1</tex>. 2)# Делим множество на две части: точки над и под прямой. 3)# Для каждой половины ищем выпуклую оболочку Грехемом с условием, что сортируем не по полярному углу, а по координате. 4)# Сливаем получившиеся оболочки.

1)# Разобьем все множество на произвольные группы по <tex>m</tex> штук в каждой. Будем считать, что <tex>m</tex> нам известно. Тогда всего групп окажется <tex>r = n / m</tex>. 2)# Для каждой группы запускаем Грехема.  3)# Начиная с самой нижней точки ищем саму выпуклую оболочку Джарвисом, но перебираем не все точки, а по одной из каждой группы.

1)# Найдем самую левую точку <tex>p_0</tex> и самую правую точку <tex>p_1</tex> (Если таких несколько, выберем среди таких нижнюю и верхнюю соответственно). 2)# Возьмем все точки выше прямой <tex>p_0 p_1</tex>. 3)# Найдем среди этого множества точку <tex>p_i</tex>, наиболее отдаленную от прямой (если таких несколько, взять самую правую). 4)# Рекурсивно повторить шаги 2-3 для прямых <tex>p_0 p_i</tex> и <tex>p_i p_1</tex>, пока есть точки. 5)# Добавить в ответ точки <tex>p_0 .. p_i .. p_1</tex>, полученные в п. 3. 6)# Повторить пункты 2-5 для <tex>p_1 p_0</tex> (то есть для "нижней" половины). 7)# Ответ - объединение списков из п. 5 для верхней и нижней половины.