Я заинтересован в реализации и изучении алгоритма Киркпатрика-Зейделя. Это подход «разделяй и властвуй» для нахождения выпуклой оболочки некоторого набора точек. Меня волнует только двумерный случай.
Я нашел интересный раздаточный материал по этой проблеме здесь:
Общие шаги алгоритма следующие:
INPUT: A set P of points on the plane.
OUTPUT: The set of points that define the convex hull.
1. Calculate median x-coordinate M of P.
2. Find the bridge segment that crosses the line x = M using the
Prune and Search Technique.
3. Trim the set based on this segment
4. Split P to sets PL, PR and recursively apply the above steps to find
the remaining segments
5. The above steps must be run twice, once for the upper hall and once
for the lower hall. Once you find both, you have the convex hull.
(1) можно найти за O(N). Это очень тривиально, особенно в C++ вы можете просто использовать nth_element с указанным компаратором
(3) также можно найти за O(N). Если найденный вами отрезок определяется точками p1 и p2, то вам просто нужно игнорировать каждую точку p, где p1.x <= p.x <= p2.x
(4) является прямым результатом (3)
(5) два рекурсивных вызова двух только что найденных подмножеств
Чтобы достичь O(nlogn) сложности этого алгоритма разделяй и властвуй. Нам нужен шаг (2), чтобы также выполнить O(n).
Согласно раздаточному материалу, этот шаг можно решить с помощью линейного программирования, и, поскольку мы работаем на плоскости, можно добиться линейного времени.
Теперь раздаточный материал объясняет часть (2) более подробно, вот шаги.
Я понимаю каждый шаг, кроме (3) и (4).
(3). Что такое b? Думаю, это не имеет значения. Поскольку вы нашли наклон m, а затем переходите к поиску опорной линии для множества P, B — это то, что вы ищете.
(4). что такое опорная линия для множества P и как ее эффективно найти?
