В вычислительной геометрии , алгоритм Чана , [1] имя Тимоти М. Чан , является оптимальным выходным чувствительным алгоритмом для вычисления выпуклой оболочки набора из точек в 2- или 3-мерном пространстве. Алгоритм принимает время, где - количество вершин выхода (выпуклой оболочки). В плоском случае алгоритм объединяеталгоритм ( например, сканирование Грэма ) с маршем Джарвиса (), чтобы получить оптимальное время. Алгоритм Чана примечателен тем, что он намного проще алгоритма Киркпатрика – Зейделя и естественным образом распространяется на трехмерное пространство. Эта парадигма [2] была независимо разработана Фрэнком Нильсеном в его докторской диссертации. Тезис. [3]
Алгоритм
Обзор
Для одного прохода алгоритма требуется параметр который находится между 0 и (количество точек нашего набора ). Идеально, но количество вершин в выходной выпуклой оболочке изначально неизвестно. Несколько проходов с увеличением значений выполняются, которые затем прекращаются, когда (см. ниже о выборе параметра ).
Алгоритм начинается с произвольного разбиения множества точек в подмножества максимум с очки каждый; Заметь.
Для каждого подмножества , он вычисляет выпуклую оболочку, , используя алгоритм (например, сканирование Грэма ), где- количество точек в подмножестве. Поскольку есть подмножества очков каждый, эта фаза занимает время.
Во время второй фазы марш Джарвиса выполняется с использованием предварительно вычисленных (мини) выпуклых корпусов,. На каждом этапе алгоритма марша Джарвиса у нас есть точка в выпуклой оболочке (вначале может быть дело в с наименьшей координатой y, которая гарантированно находится в выпуклой оболочке ), и нужно найти точку так что все остальные точки справа от линии [ требуется пояснение ] , где обозначения просто означает, что следующая точка, то есть , определяется как функция а также . Выпуклая оболочка множества, , известен и содержит не более точек (перечисленных в порядке по часовой стрелке или против часовой стрелки), что позволяет вычислить в время бинарным поиском [ как? ] . Следовательно, вычисление для всех подмножества могут быть выполнены в время. Тогда мы можем определить используя ту же технику, что обычно используется в марше Джарвиса, но только с учетом очков (т.е. точки в выпуклой мини-оболочке) вместо всего множества . По этим пунктам одна итерация марша Джарвисачто незначительно по сравнению с вычислением для всех подмножеств. Марш Джарвиса завершается, когда процесс повторяется. раз (потому что, как работает марш Джарвиса, самое большее после итераций его самого внешнего цикла, где - количество точек в выпуклой оболочке , мы должны были найти выпуклую оболочку), поэтому вторая фаза принимает время, эквивалентное время, если близко к (см. ниже описание стратегии выбора так что это так).
Выполняя две фазы, описанные выше, выпуклая оболочка баллы рассчитываются в время.
Выбор параметра
Если выбрано произвольное значение для , может случиться так, что . В этом случае послеНа втором этапе мы прерываем марш Джарвиса, так как его доведение до конца заняло бы слишком много времени. В тот момент время будет потрачено, а выпуклая оболочка не будет рассчитана.
Идея состоит в том, чтобы выполнить несколько проходов алгоритма с увеличением значений ; каждый проход завершается (успешно или безуспешно) ввремя. Еслислишком медленно увеличивается между проходами, количество итераций может быть большим; с другой стороны, если он поднимается слишком быстро, первый для которых алгоритм завершается успешно, может быть намного больше, чем , и создать сложность .
Стратегия квадратуры
Одна из возможных стратегий - возвести в квадрат значение на каждой итерации до максимального значения (соответствует разделу на синглтон-наборы). [4] Начиная со значения 2, на итерации, выбран. В этом случае, итерации выполняются, учитывая, что алгоритм завершается, как только мы
с логарифмом по основанию , а общее время работы алгоритма равно
В трех измерениях
Чтобы обобщить эту конструкцию на трехмерный случай, Вместо сканирования Грэма следует использовать алгоритм для вычисления трехмерной выпуклой оболочки по Препарате и Хонгу, а также необходимо использовать трехмерную версию марша Джарвиса. Временная сложность остается. [1]
Псевдокод
В следующем псевдокоде текст между скобками и курсивом является комментарием. Чтобы полностью понять следующий псевдокод, рекомендуется, чтобы читатель уже был знаком с алгоритмами сканирования Грэма и Марша Джарвиса для вычисления выпуклой оболочки,, множества точек, .
- Ввод: Установить с участием точки .
- Выход: Установить с участием точек выпуклая оболочка .
- (Выберите точку который гарантированно находится в : например, точка с наименьшей координатой y.)
- (Эта операция занимает время: например, мы можем просто перебрать .)
- ( используется в марше Джарвиса этого алгоритма Чана,
- чтобы вычислить вторую точку, , в выпуклой оболочке .)
- (Примечание: это не точка.)
- (Для получения дополнительной информации см. Комментарии рядом с соответствующей частью алгоритма Чана.)
- (Примечание: , количество точек в конечной выпуклой оболочке , не известно.)
- (Это итерации, необходимые для определения ценности , что является оценкой .)
- ( требуется для этого алгоритма Чана, чтобы найти выпуклую оболочку .)
- (Более конкретно, мы хотим , чтобы не выполнять слишком много ненужных итераций
- и так что временная сложность этого алгоритма Чана равна .)
- (Как объяснялось выше в этой статье, мы используем стратегию, в которой не более итерации необходимы, чтобы найти .)
- (Примечание: финальный не может быть равно , но никогда не меньше, чем и больше чем .)
- (Тем не менее, этот алгоритм Чана останавливается однажды выполняются итерации самого внешнего цикла,
- то есть, даже если , это не работает итераций самого внешнего цикла.)
- (Для получения дополнительной информации см. Часть марша Джарвиса этого алгоритма ниже, где возвращается, если .)
- дляделать
- (Установить параметр для текущей итерации. Мы используем «схему возведения в квадрат», как описано выше в этой статье.
- Есть и другие схемы: например, «схема удвоения», где , для .
- Однако, если мы воспользуемся «схемой удвоения», итоговая временная сложность этого алгоритма Чана составит .)
- (Инициализируйте пустой список (или массив) для хранения точек выпуклой оболочки , как они найдены.)
- (Произвольно разделить набор точек в подмножества примерно элементов каждый.)
- (Вычислите выпуклую оболочку всех подмножества точек, .)
- (Занимает время.)
- Если , то временная сложность .)
- дляделать
- (Вычислить выпуклую оболочку подмножества , , используя сканирование Грэма, которое берет время.)
- ( выпуклая оболочка множества точек .)
- (Здесь выпуклые оболочки соответственно подмножеств точек были вычислены.)
- (Теперь, использовать модифицированную версию о марше Jarvis алгоритм вычисления выпуклой оболочки.)
- (Марш Джарвиса выступает в время, где количество входных точек и - количество точек в выпуклой оболочке.)
- (Учитывая, что марш Джарвиса является алгоритмом , чувствительным к выходным данным, время его работы зависит от размера выпуклой оболочки,.)
- (На практике это означает, что марш Джарвиса выполняет итерации самого внешнего цикла.
- На каждой из этих итераций он выполняет не более итераций его самого внутреннего цикла.)
- (Мы хотим , поэтому мы не хотим выполнять больше, чем итераций в следующем внешнем цикле.)
- (Если наш текущий меньше чем , т.е. выпуклая оболочка Не может быть найдено.)
- (В этой модифицированной версии марша Джарвиса мы выполняем операцию внутри самого внутреннего цикла, который принимает время.
- Следовательно, общая временная сложность этой модифицированной версии составляет
- Если , то временная сложность .)
- дляделать
- (Примечание: здесь точка в выпуклой оболочке уже известно, то есть .)
- (В этом внутреннем цикле for возможные следующие точки на выпуклой оболочке , , вычисляются.)
- (Каждый из них возможные следующие точки из другого :
- это, возможная следующая точка на выпуклой оболочке который является частью выпуклой оболочки .)
- (Примечание: зависит от : то есть для каждой итерации , у нас есть возможные следующие точки на выпуклой оболочке .)
- (Примечание: на каждой итерации , только одна из точек среди добавляется к выпуклой оболочке .)
- дляделать
- ( находит точку такой, что угол максимально [ почему? ] ,
- где угол между векторами а также . Такой хранится в .)
- (Углы не нужно рассчитывать напрямую: можно использовать тест ориентации [ как? ] .)
- ( может быть выполнено в время [ как? ] .)
- (Примечание: на итерации , а также известна и является точкой в выпуклой оболочке :
- в данном случае это точка с самой низкой координатой y.)
- (Выберите точку который максимизирует угол [ почему? ] быть следующей точкой на выпуклой оболочке.)
- (Марш Джарвиса заканчивается, когда следующая выбранная точка на выпуклой оболочке, , - начальная точка, .)
- если
- (Верните выпуклую оболочку который содержит точки.)
- (Примечание: конечно, возвращать не нужно что равно .)
- возвращаться
- еще
- (Если после итераций точка не был найден так что , тогда .)
- (Нам нужно начать с более высокого значения для .)
Выполнение
Статья Чана содержит несколько предложений, которые могут улучшить практическую производительность алгоритма, например:
- При вычислении выпуклой оболочки подмножеств исключите точки, которые не находятся в выпуклой оболочке, из рассмотрения в последующих выполнениях.
- Выпуклые оболочки больших наборов точек могут быть получены путем объединения ранее вычисленных выпуклых оболочек вместо пересчета с нуля.
- При вышеупомянутой идее основная стоимость алгоритма заключается в предварительной обработке, т. Е. Вычислении выпуклой оболочки групп. Чтобы снизить эту стоимость, мы можем рассмотреть возможность повторного использования корпусов, вычисленных на предыдущей итерации, и их объединения по мере увеличения размера группы.
Расширения
Статья Чана содержит некоторые другие проблемы, известные алгоритмы которых можно сделать оптимально чувствительными к выходным данным, используя его технику, например:
- Вычисление нижнего конверта набора из отрезки линии, которая определяется как нижняя граница неограниченной трапеции, образованной пересечениями.
- Хершбергер [5] дал алгоритм, который можно ускорить до , где h - количество ребер в конверте
- Построение алгоритмов, чувствительных к выходу, для выпуклых оболочек больших размеров Используя точки группировки и эффективные структуры данных, сложность может быть достигнута при условии, что h имеет полиномиальный порядок от .
Смотрите также
Рекомендации
- ^ a b Тимоти М. Чан. « Оптимальные чувствительные к выходу алгоритмы выпуклой оболочки в двух и трех измерениях ». Дискретная и вычислительная геометрия . 16. С. 361–368. 1996 г.
- ↑ Фрэнк Нильсен. « Группировка и запросы: парадигма для получения алгоритмов, чувствительных к выходу ». Дискретная и вычислительная геометрия , LNCS 1763, стр. 250–257, 2000.
- ↑ Фрэнк Нильсен. « Адаптивная вычислительная геометрия ». Кандидат наук. диссертация, INRIA , 1996.
- ^ B. Chazelle Jiří Matoušek. « Дерандомизация чувствительного к выходу алгоритма выпуклой оболочки в трех измерениях ». Вычислительная геометрия , Vol. 5. С. 27–32. 1995 г.
- ^ Дж. Хершбергер. « Нахождение верхней огибающей n сегментов линии за время O (n log n) ». Письма об обработке информации , Vol. 33. С. 169–174. 1989 г.