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

{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
|+
|-align="center"
|'''НЕТ ВОЙНЕ'''
|-style="font-size: 16px;"
|
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.

Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.

Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.

Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.

''Антивоенный комитет России''
|-style="font-size: 16px;"
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
|-style="font-size: 16px;"
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
|}

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

{{Определение|definition='''Выпуклая оболочка''' {{---}} минимальная последовательность точек такая, что последовательное соединение этих точек дает выпуклый многоугольник, и в этом многоугольнике содержатся все точки.}}

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

[[Файл:Parallel-convexhull-not-parallel-1.png|300px|thumb|right|Как мы будем двигаться]]

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

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

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

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

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

[[Файл:Parallel-convex-hull-tangent.png|300px|thumb|right|Касательные]]

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

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

 '''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

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

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

[[Файл:Parallel-convex-hull-tangent-tangent.png|300px|thumb|right|Касательные из каждой точки]]

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

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

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

[[Файл:Parallel-convex-hull-sqrt.png|300px|thumb|right|Касательные]]

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

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

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

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

2) Если оказалось, что результаты разные, то мы берем <tex>k\sqrt{n}</tex>, <tex>k\sqrt{n} + 1</tex>, <tex>k\sqrt{n} + 2</tex>, ..., <tex>(k + 1)\sqrt{n}</tex>, и смотрим параллельно подходят ли они под условия. Каждое их них возвращает 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

Его <tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

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

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

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

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

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

<tex>work = \sqrt{n}</tex>, <tex>span = \log{n}</tex>

Итоговое время работы: <tex>work = n</tex>, <tex>span = \log{n}</tex>