Статические выпуклые оболочки: Джарвис, Грэхем, Эндрю, Чен, QuickHull

Конспект не готов.

Алгоритм Джарвиса

По-другому "Заворачивание подарка"

Описание Алгоритма

1) Возьмем самую правую нижнюю точку [math]p_0[/math] нашего множества. [math]p_0[/math] лежит в выпуклой оболочке, поэтому добавляем ее в ответ.

2) На каждом следующем шаге для последнего добавленного [math]p_i[/math] ищем [math]p_{i + 1}[/math] с максимальным полярным углом относительно [math]p_i[/math] (Если углы равны, надо сравнивать по расстоянию). Добавляем [math]p_{i + 1}[/math] в ответ. Если [math]p_{i + 1} == p_0[/math] , заканчиваем алгоритм.