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

Перейти к: навигация, поиск

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

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

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)