1632
правки
Изменения
м
rollbackEdits.php mass rollback
Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB.
Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(nlogn\log(n))</tex>
Прежде чем решать эту задачу, давайте решим такую задачу:
Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже.
Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от <tex>0 </tex> до <tex>1</tex>. Похоже на задачу бинарного поиска. Давайте опишем шаги:
'''int''' l = 0, r = n - 2
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>
