Редактирование: Параллельный алгоритм нахождения выпуклой оболочки
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 13: | Строка 13: | ||
Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB. | Мы определенно знаем, что через них будет идти выпуклая оболочка, так как если она не будет идти через них, то это значит, что есть какой то отрезок между точками, который ниже и правее A, но это не так. Аналогично для правой верхней точки. Теперь будем строить от A до B верхнюю выпуклую оболочку для всех точек выше AB, и от B до A нижнюю выпуклую оболочку для всех точек ниже AB. | ||
− | Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O( | + | Теперь рассмотрим верхнюю половину. Нижняя будет выполняться аналогично. Берем середину из самое левой точки и правой точки по координате x и делим наше множество точек на две части каким то образом. Теперь нам нужно сделать объединение двух выпуклых оболочек за <tex>O(n)</tex>, для того, что бы итоговая асимптотика была <tex>O(nlog(n))</tex> |
Прежде чем решать эту задачу, давайте решим такую задачу: | Прежде чем решать эту задачу, давайте решим такую задачу: | ||
Строка 25: | Строка 25: | ||
Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже. | Мысленно представим соединение всех точек многоугольника с данной нам точкой. Заметим, что если мы воспользуемся [[Предикат_"левый_поворот"|предикатом "левый поворот"]], то сможем понять, находится ли точка, являющаяся касательной правее или левее, просто взяв предикат по точке куда ведем пересечение, данной точкой и следующей за точкой пересечения точкой. Проще говоря, нам нужно понять, "выше" ли находится прямая со следующей точкой или нет. Если оказалось, что она выше, то касательная находится выше. Если ниже, то касательная находится ниже. | ||
− | Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от | + | Таким образом, мы можем за <tex>O(1)</tex> понимать для точки, дальше ли ее точка касательной или она была раньше. То есть у нас есть унимодальная функция, и нам нужно найти переход от 0 до 1. Похоже на задачу бинарного поиска. Давайте опишем шаги: |
'''int''' l = 0, r = n - 2 | '''int''' l = 0, r = n - 2 | ||
Строка 35: | Строка 35: | ||
r = m | r = m | ||
− | Нахождение касательной из точки на многоугольник работает за <tex>O( | + | Нахождение касательной из точки на многоугольник работает за <tex>O(log(n))</tex> |
{{Задача | {{Задача | ||
|definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже. | |definition = Нам дано два выпуклых многоугольника A и B, которые были разрезаны отрезком X, и взята верхняя часть. Нужно провести такую касательную через 2 точки многоугольника, что все точки находятся либо на касательной либо ниже. | ||
}} | }} | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
==Параллельный алгоритм== | ==Параллельный алгоритм== | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |