Одним из самых простых алгоритмов построения выпуклой оболочки является алгоритм Джарвиса.
Выберем какую-нибудь точку $p_0$, которая гарантированно попадёт в выпуклую оболочку. Например, нижнюю, а если таких несколько, то самую левую из них.
Дальше будем действовать так: найдём самую «правую» точку от последней добавленной (то есть точку с минимальным полярным углом относительно неё) и добавим её в оболочку. Будем так итеративно добавлять точки, пока не «замкнёмся», то есть пока самой правой точкой не станет $p_0$.
Корректность алгоритма легко доказывается по индукции:
- На нулевом шаге мы выбрали точку, точно лежащую в выпуклой оболочке.
- На $i$-м шаге мы взяли такую точку, что все остальные лежат по левую сторону отрезка $(p_{i-1}, p_i)$, и поэтому точно не перекрывают точку $p_i$.
Алгоритм Джарвиса также называют методом заворачивания подарка: мы как бы проходимся вокруг множества с оберткой, которая естественным образом заворачивается вокруг каждого следующего угла.
Для простоты, будем считать, что все точки различны, имеют целочисленные координаты, а также что нет трёх точек на одной прямой.
vector<r> jarvis(vector<r> points) {
r p0 = points[0];
for (r p : points)
if (p.x < p0.x || (p.x == p0.x && p.y < p0.y))
p0 = p;
vector<r> hull = {p0};
while (true) {
r t = p0; // кандидат на следующую точку
for (r p : points)
// лучше никакие полярные углы не считать
if ((p - p0) ^ (t - p0) > 0)
t = p;
if (t == p0)
continue;
else {
p0 = t;
hull.push_back(t);
}
}
return hull;
}
Для каждой точки выпуклой оболочки (обозначим их количество за $h$) мы из всех оставшихся $O(n)$ точек будем искать оптимальную, что суммарно будет работать за $O(n h)$.
Важно помнить, что асимптотика именно $O(nh)$, а не $O(n^2)$: существуют задачи, где оболочка маленькая, и это существенно.
Задача. Дано множество точек, по которому итеративно строят выпуклую оболочку и удаляют те точки, которые в неё попали. Для каждой точки требуется определить, после какой итерации она будет удалена. Асимптотика $O(n^2)$.