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

Одним из самых простых алгоритмов построения выпуклой оболочки является алгоритм Джарвиса.

Выберем какую-нибудь точку $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)$ .