Параллельный алгоритм нахождения выпуклой оболочки

Задача:

Пусть нам даны точки на плоскости. Нужно найти выпуклую оболочку на этих точках.

Определение:

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

Последовательный алгоритм

Как мы будем двигаться

Давайте первым делом найдем самую левую A (при нескольких таких выбрать нижнюю) и самую правую B (при нескольких таких выбрать самую верхнюю) точку на плоскости.

Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.

Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за [math]O(n)[/math], для того, что бы итоговая асимптотика была [math]O(n\log(n))[/math]

Прежде чем решать эту задачу, давайте решим такую задачу:

Задача:

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

Касательные

Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся предикатом "левый поворот", то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.

Таким образом, мы можем за [math]O(1)[/math] понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от [math]0[/math] до [math]1[/math]. Похоже на задачу бинарного поиска. Давайте опишем шаги:

int l = 0, r = n - 2
while 1 < r - l:
    m = (l + r) / 2
    if left_turn(a[m], K, a[m + 1]) > 0:
        l = m
    else:
        r = m

Нахождение касательной из точки на многоугольник работает за [math]O(\log(n))[/math]

Задача:

Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже.

Касательные из каждой точки

Давайте мысленно проведем касательные из каждой точки A на многоугольник B. Только одна из них является истинной. Здесь будет работать примерно такая же стратегия, что и в прошлом. Если мы понимаем с помощью предиката левого поворота, что касательная выше, то правильная точка находится до нашей, иначе дальше нашей. Снова сделаем бинпоиск. Только на сей раз проверка на то, что точка находится левее/правее нужной будет требовать от нас [math]O(log(n))[/math]. Таким образом, алгоритм нахождения общей касательной будет работать за [math]O(log^2(n))[/math].

Теперь мы можем соединять две выпуклые оболочки в одну просто проводя касательную между ними и выпиливая у первого многоугольника все, что дальше точки касания, а у второго многоугольника все, что находится до точки касания за [math]O(n)[/math]. Задача решена.

Параллельный алгоритм

Касательные

Теперь нам нужно это как то ускорить. Давайте посмотрим, что же мы можем делать параллельно, и при этом не ухудшим асимптотику. Конечно же, у нас был поиск касательной за [math]O(log^2(n))[/math], а можно сделать его за [math]work = O(n)[/math], при этом уменьшив span

Посмотрим на каждую фазу бинпоиска. Заметим, что мы можем просто не брать бинпоиск, а разделить массив рассмотрения на [math]\sqrt{n}[/math] частей.

Для каждого элемента посмотрим его результат (поймем, выше ли реальная касательная), и, если оказалось, что у нас и у точки, которая находится на [math]\sqrt{n}[/math] различные результаты, то мы поймем, что правильный результат находится между нами. То есть мы возьмем все точки, которые находятся между нами, если у нас с соседом разные результаты и снова у каждой точки посмотрим, где находится верный результат. В этот раз мы уже точно узнаем результат, ведь теперь недостающих точек нет. То есть алгоритм будет такой:

1) Берем [math]\sqrt{n}[/math], [math]2\sqrt{n}[/math], [math]3\sqrt{n}[/math], ..., [math]\sqrt{n}\sqrt{n}[/math] и параллельно проверяем, подходят ли они под условие. Каждая из них возвращает [math]0[/math] или [math]1[/math] - левее или правее они результата. Каждый результат считает за себя [math]k\sqrt{n}[/math] и за соседа [math](k + 1)\sqrt{n}[/math].

2) Если оказалось, что результаты разные, то мы берем [math]k\sqrt{n}[/math], [math]k\sqrt{n} + 1[/math], [math]k\sqrt{n} + 2[/math], ..., [math](k + 1)\sqrt{n}[/math], и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 0 или 1 - левее или правее находится результат. В точке, где меняет 0 и 1 и есть верный ответ.

Таким образом, у нас выходит примерно такой алгоритм -

1) Создаем функцию, которая находит касательную для точки из первого многоугольника на второй многоугольник.

fun getFromPoint(K):
    int startAfter
    pfor i = 0...sqrt(n):
        int startCurrent = sqrt(n) * i
        int startNext = sqrt(n) * i + 1
        int finishCurrent = sqrt(n) * i
        int finishNext = sqrt(n) * i + 1
        boolean isStartBeforeAnswer = left_turn(startCurrent, K, startNext) > 0
        boolean isFinishBeforeAnswer = left_turn(finishCurrent, K, finishNext) > 0
        if (isStartBeforeAnswer != isFinishBeforeAnswer) startAfter = startCurrent
    pfor i = 0..sqrt(n):
        int start = i + startAfter
        int middle = i + startAfter + 1
        int finish = i + startAfter + 2
        if (left_turn(start, K, middle) != left_turn(middle, K, finish)) return middle

Его [math]work = \sqrt{n}[/math], [math]span = \log{n}[/math]

2) Создадим функцию, которая находит касательную $AB$ между двумя многоугольниками (она будет сильно похожа на предыдущую функцию)

Теорема:

Если предыдущая точка $prev$ и следующая точка $next$ лежат по одну сторону (в нашем случае ниже) от касательной на второй многоугольник, то эта точка $x$ является точкой искомой касательной. Иначе - если $prev$ находится выше касательной, то мы дальше $A$, иначе - до $A$.

Доказательство:

[math]\triangleright[/math]

Многоугольник выпуклый, значит, что если одна точка лежит на прямой, а две соседние по одну сторону от нее, значит, что эта прямая является касательной. Если $prev$ находится выше касательной, то это значит, что его касательная находится выше, значит, что AB тоже находится выше, а значит, что A находится раньше. Аналогично для обратного случая.

[math]\triangleleft[/math]

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

[math]work = \sqrt{n}[/math], [math]span = \log{n}[/math]

Итоговое время работы: [math]work = n[/math], [math]span = \log{n}[/math]