Выпуклые оболочки

Выпуклые оболочки

Выпуклое множество — такое множество точек, что, для любых двух точек множества, все точки на отрезке между ними тоже принадлежат этому множеству.

Выпуклая оболочка множества точек — такое выпуклое множество точек, что все точки фигуры также лежат в нем.

Минимальная выпуклая оболочка множества точек — это минимальная по площади выпуклая оболочка.

Для экономии времени дальше минимальные выпуклые оболочки мы будем называть просто выпуклыми оболочками.

Для практических целей выпуклые оболочки полезны тем, что компактно хранят всю необходимую информацию о множестве точек, что позволяет быстро отвечать на разнообразные запросы на этом множестве.

Научимся их строить по какому-то множеству из \(n\) точек на плоскости.

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

Выберем какую-нибудь точку \(p_0\), которая гарантированно попадёт в выпуклую оболочку. Например, нижнюю, а если таких несколько, то самую левую из них.

Дальше будем действовать так: найдём самую «правую» точку от последней добавленной (то есть точку с минимальным полярным углом) и добавим её в оболочку. Будем так итеративно добавлять точки, пока не «замкнёмся», то есть пока самой правой точкой не станет \(p_0\).

alt text
alt text

Корректность алгоритма легко доказывается по индукции:

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

Для каждой точки выпуклой оболочки (обозначим их количество за \(h\)) мы из всех оставшихся \(O(n)\) точек будем искать оптимальную, что суммарно будет работать за \(O(n h)\).

В реализации будем пользоваться тем же классом для точки, что и в статье про вычислительную геометрию.

Для краткости, будем считать, что все точки различны, имеют целочисленные координаты, а также что нет трёх точек на одной прямой.

vector<r> jarvis_convex_hull(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;
}

Важно помнить, что асимптотика именно \(O(nh)\), а не \(O(n^2)\): существуют задачи, где оболочка маленькая, и это существенно.

Алгоритм Грэхема

Алгоритм Грэхема — это оптимизация алгоритма Джарвиса, основанная на следующем наблюдении: если отсортировать все точки по полярному углу относительно точки \(p_0\), то выпуклая оболочка будет какой-то подпоследовательностью такого отсортированного массива точек.

Алгоритм последовательно строит выпуклые оболочки для каждого префикса этого отсортированного масива. При добавлении \(i\)-й точки в оболочку нужно удалить сколько-то последних добавленных точек, которые не будут входить в новую оболочку. Чтобы это делать эффективно, мы можем хранить выпуклую оболочку в стэке и в цикле while смотреть на три последние точки и проверять, образуют ли они правый поворот. Если это так, то среднюю следует удалить — мы нашли треугольник \((p_0, p_i, p_{i-2})\), который содержит \(p_{i-1}\), значит её можно удалить.

alt text
alt text

Каждая точка будет добавлена один раз удалена не более одного раза, что занимает константное количество операций. Соответственно, время работы будет упираться во время работы сортировки, то есть \(O(n \log n)\).

vector<r> graham_convex_hull(vector<r> points) {
    // находим p0, как и раньше
    r p0 = points[0];
    for (r p : points)
        if (p.x < p0.x || (p.x == p0.x && p.y < p0.y))
            p0 = p;
 
    // TODO: удалить p0

    // сортируем точки по полярному углу    
    sort(points.begin(), points.end(), [&](r a, r b){
        return (a - p0) ^ (b - p0) > 0;
    });
    
    vector<r> s = {p0};
    for (r p : points) {
        while (...) {
             s[s.size()-2] = s[s.size()-1];
             s.pop_back();            
        }
        s.push_back(p);
    }
    
    return s;
}

Верхние и нижние огибающие

Для некоторых на самом деле нам нужны не выпуклые оболочки, а только половины. Их называют огибающими.

Огибающие строить проще. В некоторых задачах, где точки генерируются за линейное время, это м.

vector<r> upper_envelope(vector<r> points) {
    sort(points.begin(), points.end(), [](r a, r b){
        return a.x < b.x;
    });
    
    vector<r> s = {p0};
    for (r p : points) {
        while (...) {
            s[s.size()-2] = s[s.size()-1];
            s.pop_back();
        }
        s.push_back(p);
    }
    
    return s;
}

Алгоритм Эндрю

Для построения выпуклой оболочки также можно поступить следующим образом: построить верхнюю огибающую, нижнюю огибаюзую, а потом просто объединить два списка.

vector<r> andrew_convex_hull(vector<r> points) {
    vector<r> lower = // ...
    vector<r> upper = // ...
    vector<r> hull = lower;        
}

Вообще, с огибающими работать немного проще, чем с оболочками

Пересечение полуплоскостей

Например, так можно строить подобные клёвые картинки:

Алгоритм Чана

Алгоритм Чана — это объединение алгоритмов Джарвиса и Грэхэма (или Эндрю) .

Разделим все точки на группы по \(m\) точек в каждой. В каждой группе построим выпуклую оболочку за \(O(m \log m)\). Точки никак не упорядочены, и эти оболочки могут пересекаться, это нормально. Суммарно для всех групп понадобится \(O(n \log m)\).

Затем, так же начиная с самой левой нижей точки, мы будем строить общую выпуклую оболочку алгоритмом Джарвиса, но теперь «самую правую точку» можно находить каждый раз не за \(O(n)\), а за \(O(\frac{n}{m} \log m)\), если делать бинарный поиск в каждой из \(\frac{n}{m}\) оболочек.

Такое решение будет работать за \(O(h \frac{n}{m} \log m + n \log m)\). Если заранее примерно знать \(h\), то можно положить \(m = h\), и тогда асимптотипа составит \(O(n \log h)\).

Динамические выпуклые оболочк