Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
3.5. Замечания и комментарии
179
сортировки. При каждом подходящем случае мы иллюстрировали эту аналогию, делая соответствующие примечания. В этом разделе мы воспользуемся удобным случаем, чтобы дать более систематический обзор алгоритмов, представленных в этой главе, раскрывая соответствующие им методы сортировки.
Уместно сделать следующее замечание. Если смотреть более строго, то аналогия будет довольно полной, когда все заданные точки являются вершинами выпуклой оболочки. Это вполне понятно, так как в задаче сортировки нет аналога для внутренних точек выпуклой оболочки.
В алгоритме Грэхема сортировка используется явным образом в самом начале работы. Первый алгоритм из разд. 3.3.1, проверяющий каждую пару точек для определения, образуют они или нет ребро выпуклой оболочки (и настолько не эффективный, что мы даже не удостоили его собственного имени), аналогичен следующему необычному алгоритму сортировки:
1. Для того чтобы отсортировать числа х\, хц, нужно сначала найти наименьшее по величине хт и поменять местами Х\ и хт. (Требуемое время — O(N).)
2. Теперь нужно найти число, которое в окончательно отсортированном списке будет следовать за Xi, просматривая возможных кандидатов х2, ..., xN. Число х,- следует за хх тогда и только тогда, когда между ними нет других элементов списка. (Требуемое время — 0(N2).)
3. Аналогичным образом найти элементы, следующие за х2, . . ., Xjv-i- (Время, требуемое для нахождения каждого последующего элемента, — 0(N2). Полное время — 0(N3).)
Эта процедура может быть очевидым образом улучшена за счет ускорения процесса поиска последующего элемента. Для того чтобы определить элемент, следующий за xi, необходимо лишь найти наименьший элемент среди xi+\, . . . , xN. После такого изменения приведенный выше алгоритм превращается в СОРТИРОВКУ ПОСРЕДСТВОМ ВЫБОРА [Knuth (1973)] и соответствует алгоритму Джарвиса (разд. 3.3.3).
Алгоритмы построения выпуклой оболочки, основанные на методе «разделяй и властвуй», разбивающие исходное множество точек на две части, строящие выпуклую оболочку для каждой из этих частей и затем объединяющие их за линейное время, являются геометрическими аналогами алгоритма сортировки слиянием. Алгоритм, строящий выпуклую оболочку в реальном времени, является аналогом алгоритма сортировки вставками. Аналоги алгоритма быстрой сортировки обсуждались в разд. 3.3.4.
Хотя Q(N log N) является нижней оценкой сложности в худшем случае для любого алгоритма построения выпуклой обо-
180
Гл. 3. Выпуклые оболочки: основные алгоритмы
л очки множества S, содержащего N точек, тем не менее в слу чае, когда число крайних точек h существенно меньше N, по видимому, можно достигнуть меньшей сложности. Это соображение с большим успехом использовали Киркпатрик и Зейдель, разработавшие алгоритм со сложностью О (N log К) и предложившие его в качестве «предельного». Они также доказали, что этот алгоритм является асимптотически оптимальным (Kirk patrick, Seidel (1983)]. Их алгоритм отдельно строит верхнюю и нижнюю оболочки. Рас
ШаЦр)
смотрим построение верхне] оболочки. Исходное множе ство разбивается надверав ные части, отделимые друг от друга вертикальной прямой. Затем вместо рекурсивного построения верхней оболочки для каждой из двух частей и последующего вычисления общей опорной прямой (называемой верхним соединением) алгоритм сначала строит это соединение, а затем раздельно строит верхние оболочки для подмножеств точек, расположенных соответственно слева и справа от левого и правого концов соединения. Ключевым моментом этого метода является эффективный способ построения соединения. Опираясь на то, что соединение можно определить в результате решения задачи линейного программирования, авторы алгоритма воспользовались методом решения задач линейного программирования за линейное время, который был недавно предложен Меджиддо и Дайером и подробно будет рассмотрен в разд. 7.2.5. Обозначим через h\ и h2 (hi + h2 = h) число вершин оболочки соответственно слева и справа от соединения, а через T(N,h) время выполнения алгоритма. Легко проверить, что следующее рекуррентное соотношение:
T(N, h) = cN+ max (T(N/2), h{) -f- T (N/2, Л,)),
3.33. Построение опорных п поиску пересечения е ространстве.
где с — константа, имеет решение T(N, h) = О (log h).
Лишь совсем недавно задаче построения выпуклой оболочки в Ed было уделено значительное внимание. Анализ алгоритма Чанда — Капура, выполненный Бхаттачарья, и метод «под-над», предложенный Кейли, представляют два примера возрождения
3.6. Упражнения
181
интереса к этой проблеме. Зейдель [Seidel (1981)] независимо и почти одновременно разработал алгоритм, аналогичный алгоритму Кейли. Зейдель применил аналогичный подход, но только в двойственном пространстве (см. разд. 1.3.3). Основную идею алгоритма для случая d = 2 иллюстрирует рис. 3.33, где показано, что построение опорных прямых из точки р к многоугольнику Р эквивалентно в двойственном пространстве определению пересечения dual(P) с А\ха\{р). Сложность эффективного алгоритма вычисления указанного пересечения в Ed равна О (JyL(d+1)/2J). Эта оценка была улучшена Кейли до О (NLd,2+u), которая в действительности является оптимальной для четных d (О (iVLd/2J) — размер получаемого результата).
