Вычислительная геометрия: Введение - Препарата Ф.
ISBN 5-03-001041-6
Скачать (прямая ссылка):
Рис. 3.8. Ребро выпуклой оболочки не может разделять множество точек на части, pq является ребром выпуклой оболочки, так как все точки множества располагаются по одну сторону от него; p'q' не является ребром выпуклой оболочки, так как по обе стороны от него имеются точки.
Предположим, что, как и в разд. 3.3.2, найдена наименьшая в лексикографическом порядке точка р\ заданного множества точек. Эта точка заведомо является вершиной оболочки, и теперь хотелось бы найти следующую за ней вершину р2 выпуклой оболочки\Дочка р% — это точка, имеющая наименьший положительный полярный угол относительно точки pi как начала координат. Аналогично следующая точка рз имеет наименьший полярный угол относительно точки р2 как начала-координат, и каждая последующая точка выпуклой оболочки может быть найдена за линейное время. Алгоритм Джарвиса обходит кругом выпуклую оболочку (отсюда и соответствующее название — обход Джарвиса), порождая в нужном порядке последовательность крайних точек, по одной точке на каждом шаге (рис. 3.9). Таким образом строится часть выпуклой оболочки (ломаная линия) от наименьшей в лексикографическом порядке точки (pi на рис. 3.9) до наибольшей в лексикЪграфическом порядке точки (р4 на том же рисунке). Построение' выпуклой оболочки завершается нахождением другой ломаной, идущей из наибольшей в лексикографическом порядке точки в наименьшую в лексикографическом порядке точку. Ввиду симметричности этих
3.3. Алгоритм построения выпуклой оболочки
135
двух этапов необходимо изменить на противоположные направления осей'координат и иметь дело теперь с полярными углами, наименьшими относительно отрицательного направления оси х.
Как уже было показано в разд. 3.3.1, наименьший угол может быть найден с использованием лишь арифметических операций и сравнений, не прибегая к явному вычислению значений полярных углов.
Так как все N точек множества могут лежать на его выпуклой оболочке (быть ее вершинами), а алгоритм Джарвиса затрачивает на нахождение каждой точки оболочки линейное
Рис. 3.9. Построение выпуклой оболочки методом Джарвиса. Алгоритм Джарвиса находит последовательные вершины оболочки путем многократного вычисления угла поворота. Каждая новая вершина определяется за время 0{N).
время, то время выполнения алгоритма в худшем случае равно 0(N2), что хуже, чем у алгоритма Грэхема. Если в действительности число вершин выпуклой оболочки равно h, то время выполнения алгоритма Джарвиса будет O(hN), и он очень эффективен, когда заранее известно, что значение h мало. Например, если оболочка заданного множества является многоугольником с произвольным постоянным числом сторон, то ее можно найти за линейное относительно числа точек время. Этот факт чрезвычайно важен в свете анализа сложности алгоритмов построения выпуклой оболочки в среднем, который будет представлен в следующей главе.
Другое уместное здесь замечание состоит в том, что идея поиска последовательных вершин оболочки с помощью многократного применения процедуры определения минимального угла интуитивно ассоциируется с завертыванием двумерного предмета. В действительности метод Джарвиса можно рассматривать как
136 Гл. 3. Выпуклые оболочки: основные алгоритмы
двумерный вариант подхода, основанного на идее «заворачивания подарка» и предложенного Чандом и Капуром [Chand, Ка-pur (1970)] еще до появления работы Джарвиса. Метод «заворачивания подарка» применим также в случае пространств размерности большей двух, и в общих чертах он будет рассмотрен в разд. 3.4.1.
3.3.4. Быстрые методы построения выпуклой оболочки
Задача сортировки является источником вдохновения при выработке идей решения задачи построения выпуклой оболочки. Так, например, в ряде методов, независимо предложенных почти в одно и то же время [Eddy (1977); Bykat (1978); Green, Silverman (1979); Floyd (частное сообщение, (1976)], легко угадывается основная идея (с небольшими вариациями) алгоритма быстрой сортировки БЫСТРСОРТ1). Ввиду их близкого сходства с алгоритмом БЫСТРСОРТ мы выбрали для них общее название — быстрые методы построения выпуклой оболочки, или БЫСТРОБОЛ-методы.
Чтобы лучше понять эту аналогию, коротко напомним механизм алгоритма БЫСТРСОРТ [Ноаге (1962)]. Имеется массив из N чисел, и необходимо разбить его на левый и правый под-массивы так, чтобы каждый элемент первого подмассива не превосходил каждый из элементов второго подмассива. Это делается с помощью двух указателей на элементы массива, установленных в начале соответственно на два крайних элемента и перемещаемых навстречу друг другу на один элемент за один шаг обработки. Каждый раз, когда элементы, на которые указывают указатели, не удовлетворяют требуемому порядку, производится перестановка этих элементов. Указатели двигаются попеременно — один двигается, а другой остается на месте. После каждой выполненной перестановки указатели меняются ролями. При достижении указателями одного и того же элемента массив оказывается разбитым на два подмассива, и затем к каждому из них по отдельности применяется та же самая процедура. Как хорошо известно, такой подход является очень эффективным (обработка завершается за время О (N log N)), если каждый массив разбивается на приблизительно равные части.
