Комбинаторные алгоритмы вычислительной геометрии Рандомизированный алгоритм построения выпуклой оболочки

алгоритмы Рандомизированная пошаговая конструкция: n объектов, составляющих входные данные к задаче,

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

которые нужно отсортировать.
Схема сортировки:
После i-ого из n шагов (1

< i < n) имеем i вставленных чисел в отсортированном списке.
Эти i отсортированных чисел разобьют ранги (n-i) еще не отсортированных чисел на (i+1) интервалов.
(i+1)-ый шаг состоит в выборе одного из (n-i) еще не отсортированных чисел случайным образом и вставки его в отсортированный список.

число?

Мы вставляем число х, указатель которого указывает на интервал

I.
При вставке х, мы имеем три задачи:
найти все числа, указатели которых указывают на I;
(2) обновить указатели всех чисел, чьи указатели указывают на I;
(3) удалить указатель от х к I.

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

список.
При анализе i-ого шага прямого алгоритма мы представляем, что удаляется одно из i чисел в
отсортированном списке и обновляются указатели.
Работа по обновлению указателей в этом случае такая же, как если бы алгоритм выполнялся вперед как обычно.
Ключевой момент в обратном анализе:
так как в первоначальном алгоритме числа были добавлены в произвольном порядке,
то в обратном анализе мы можем принять, что каждое число в отсортированном списке равновероятно может быть удалено на этом шаге.

Рандомизированная пошаговая сортировка

обновлены на этом шаге?
Так как у нас i интервалов

и (n-i+1) указателей, оставшихся после удаления, то ожидаемое число указателей, которые были изменены на i-ом шаге - О((n-i)/i), которое есть О(n/i).
Просуммируем проделанную работу по всем шагам и получим верхнюю границу математического ожидания полной работы. Так как



где γ - константа Эйлера, то получаем O( ) =
= О(n lоg n).

Рандомизированная пошаговая сортировка

точек на плоскости;
conv(S) – выпуклая оболочка множества S;
Для упрощения

предполагаем, что в S нет трех точек лежащих на одной прямой

Найти точку р0 во внутренней области conv(S) - это центр

масс треугольника conv(S3).
3. Для каждой точки p определить ребро conv(S3), пересекаемое отрезком pp0, и сформировать двунаправленный указатель от р на ребро и обратно. При это исключить из дальнейшего рассмотрения точки, находящиеся внутри conv(S3).

Рандомизированный алгоритм построения выпуклой оболочки

образом точку pi из S\Si-1;
Найти в conv(Si-1) вершину v1, которая

является левой соседней (опорной) для pi в conv(Si). В процессе поиска запомнить в списке recheck указатели от удаляемых ребер;
Найти в conv(Si-1) вершину v2, которая является правой соседней (опорной) для pi в conv(Si), дополнив при этом список recheck указателями от удаляемых ребер;
Вставить pi в выпуклую оболочку, сформировав conv(Si);
Для каждой точки , указатель на которую содержится в списке recheck, обновить её указатель на ребро conv(Si), пересекаемое отрезком рр0, указав его на [pi,v1] или [pi,v2]. При этом исключить из дальнейшего рассмотрения точки, которые попадают внутрь conv(Si);
}

выпуклой оболочки n точек на плоскости - О(n log2 n).

Рандомизированный алгоритм построения выпуклой оболочки