Алгоритмы - построение и анализ (1021735), страница 221
Текст из файла (страница 221)
Для сортировки полярных углов методом слияния или пирамидальной сортировки, а также сравнения углов с помощью векторного произведения, как описано в разделе 33.1, в строке 2 требуется время 0 (и !я п). (Все точки с одним и тем же значением полярного угла, кроме самой удаленной, можно удалить в течение времени О (и).) Выполнение строк 3-5 занимает время О (1). В силу неравенства гп < п — 1 цикл !ог в строках 6-9 выполняется не более п — 3 раз. Так как выполнение процедуры Рози занимает время 0(1), на выполнение каждой итерации требуется время 0(1), если не принимать во внимание время, затраченное на выполнение цикла зг!и!е в строках 7 — 8.
Таким образом„общее время выполнения цикла 1ог равно О (п), за исключением времени выполнения вложенного в него цикла згййе. Покажем с помощью группового анализа, что для выполнения всего цикла ий!!е потребуется время 0(п). При ! = 0,1,...,гл каждая точка р; попадает в стек Я ровно по одному разу. Как и при анализе процедуры Мыт!Рог в разделе 17.1, нетрудно заметить, что каждой операции Розн соответствует не более одной операции РоР. По крайней мере три точки (ро, р1 и р ) никогда не снимаются со стека, поэтому всего выполняется не более гп — 2 операций Рог.
В каждой итерации цикла згн!!е выполняется одна операция Рог, следовательно, всего этих итераций не более гп — 2. Так как проверка в строке 7 занимает время 0(1), каждый вызов Рор также требует О (1) времени, и в силу неравенства т < п — 1, полное время, которое требуется для выполнения цикла зяЫ!е, равно О (и). Таким образом, время выполнения процедуры ОкАнАМ Ясли составляет О (и !8 и). Обход по Джарвису При построении выпуклой оболочки множества точек Я путем обкода ло Джарвису (Уагч1з'з шаге!з) используется метод, известный как упаковка лаке>ил (рас!сабе старр!п8) или упаковка подарка (81Й итарр!пб). Время выполнения алгоритма равно 0 (пй), где й — количество вершин СН (Я). В том случае, когда Ь равно о (!8 и), обход по Джарвису работает быстрее, чем сканирование по Грэхему. Интуитивно обход по Джарвису моделирует обертывание плотного куска бумаги вокруг множества Я.
Начнем с того, что прикрепим конец бумаги к нижайшей точке множества, т.е. к той же точке рс, с которой начинается сканирование по Грэхему. Эта точка является вершиной выпуклой оболочки. Натянем бумагу вправо, Часть ЧИ. Избранные темы 1072 Левая цепь, Правая цепь Левая цепь ' Правая цепь Рис. 33.9. Работа алгоритма обхода по Джарвису чтобы она не провисала, после чего переместим ее вверх до тех пор, пока она не коснется какой-то точки. Эта точка также должна быть вершиной выпуклой оболочки. Сохраняя бумагу натянутой, продолжим наматывать ее на множество вершин, пока не вернемся к исходной точке ро.
Если говорить более формально, то при обходе по Джарвису строится последовательность Н = (ро, ры..., рь 1) вершин СН Я). Начнем с точки ро. Как видно из рис. 33.9, следующая вершина выпуклой оболочки р1 имеет наименьший полярный угол относительно точки ро. (При наличии совпадений выбирается точка, самая удаленная от точки ро.) Аналогично, точка рз имеет наименьший полярный угол относительно точки р1 и т.д. По достижении самой высокой вершины, скажем, рь (совпадения разрешаются путем выбора самой удаленной из таких вершин), оказывается построенной (рис. 33.9) правая цепь (пя)п сиваш) оболочки СН Я). Чтобы сконструировать левую цепь (1ей сиваш), начнем с точки рь и выберем в качестве рь+1 точку с наименьшим полярным углом относительно точки ры но относительно отрицательного нанравления оси х.
Продолжаем выполнять зту процедуру, отсчитывая полярный угол от отрицательного направления оси х, пока не вернемся к исходной точке ро. Обход по Джарвису можно было бы реализовать путем единообразного обхода вокруг выпуклой оболочки, т.е. не прибегая к отдельному построению правой и левой цепей. В такой реализации обычно отслеживается угол последней стороны выпуклой оболочки и накладывается требование, чтобы последовательность Глава 33. Вычислительная геометрия 1073 углов, образованных сторонами оболочки с положительным направлением оси х строго возрастала (в интервале от 0 до 2к радиан).
Преимущество конструирования отдельных цепей заключается в том, что исключается необходимость явно вычислять углы; для сравнения углов достаточно методов, описанных в разделе 33.1. При надлежащей реализации время выполнения обхода по Джарвису равно О (пЛ). Для каждой из Ь вершин оболочки СН(Я) находится вершина с минимальным полярным углом. Каждое сравнение полярных углов длится в течение времени 0 (1), если используются методы, описанные в разделе 33.1.
Как показано в разделе 9.1, если каждая операция сравнения выполняется в течение времени О (1), то выбор минимального из и значений занимает время 0 (и). Таким образом, обход по Джарвису длится в течение времени 0 (пй). УПРажНЕНИЯ 33.3-1. Докажите, что в процедуре ОкАнлм Бслн точки р1 и р должны быть вершинами СН Я).
33.3-2. Рассмотрим модель вычислений, которая поддерживает сложение, сравнение и умножение и в которой существует нижняя граница времени сортировки и чисел, равная й (п1яп). Докажите, что в такой модели й (и! ли) — нижняя граница времени вычисления вершин выпуклой оболочки множества и точек в порядке их обхода. 33.3-3. Докажите, что в заданном множестве точек Я две самые удаленные друг от друга точки должны быть вершинами СН (Я). 33.3-4. Для заданного многоугольника Р и точки д на его границе тенью (злаботч) точки д называется множество точек г, для которых отрезок 9г полностью находится на границе или во внутренней области многоугольника Р.
Многоугольник Р называется звездоодразиым (зшг-зларед), если в его внутренней области существует точка р, которая находится в тени любой точки, лежащей на границе этого многоугольника. Множество всех таких точек называется ядром (кегле1) многоугольника Р. На рис. 33.10 приведены примеры двух многоугольников. В части а показан звездообразный многоугольник. Отрезок, соединяющий точку р с любой из принадлежащих границе многоугольника точек д пересекает эту границу только в точке д.
В части б рисунка приведен многоугольник, не являющийся звездообразным. Выделенная серым цветом левая область является тенью точки 9, а выделенная правая область — тенью точки д'. Поскольку эти области не перекрываются, ядро является пустым. Пусть звездообразный и-угольник Р задан своими вершинами, перечисленными в порядке обхода против часовой стрелки. Покажите, как построить СН (Р) за время 0 (и). Часть ЧП.
Избранные темы 1074 6) а) Рис. 33.10. Определение звездообразного многоугольника, о котором идет речь в упражнении 33.3-4 33.3-5. В олератаеной задаче о выпуклой оболочке (оп-1ше сопчех-Ьп!1 ргоЬ1еш) параметры каждой из и точек из заданного множества Я становятся известны по одной точке за раз. После получения сведений об очередной точке строится выпуклая оболочка тех точек, о которых стало известно к настоящему времени. Очевидно, можно было бы применять сканирование по Грэхему к каждой из точек, затратив при этом полное время, равное 0 (пз 1кп). Покажите, как решить оперативную задачу о выпуклой оболочке за время О (тР).
* 33.3-6. Покажите, как реализовать инкрементный метод построения выпуклой оболочки таким образом, чтобы время его работы было равно 0 (и 1я и). 33.4 Поиск пары ближайших точек Теперь рассмотрим задачу о поиске в множестве Я, состоящем из и > 2 точек, пары ближайших друг к другу точек. Термин "ближайший" относится к обычному евклидову расстоянию: расстояние между точками р) = (х), у)) и рз = (хз, уз) равно .
Две точки в множестве Я могут совпадать; в этом случае расстояние между ними равно нулю. Эта задача находит применение, например, в системах управления транспортом. В системе управления воздушным или морским транспортом может понадобиться узнать, какие из двух транспортных средств находятся друг к другу ближе всего, чтобы предотвратить возможное столкновение между ними. В алгоритме, который работает "в лоб", просто перебираются все (~) = О (пз) пар точек.
В данном разделе описывается решение этой задачи с помощью алгоритма разбиения. Время решения этим методом определяется знакомым рекуррентным соотношением Т(т)) = 2Т(п/2) + О (и). Таким образом, время работы этого алгоритма равно 0 (и 1я и).
Глава 33. Вычислительная геометрия 1075 Алгоритм декомпозиции В каждом рекурсивном вызове описываемого алгоритма в качестве входных данных используется подмножество Р Я~ и массивы Х и У, в каждом из которых содержатся все точки входного подмножества Р. Точки в массиве Х отсортированы в порядке монотонного возрастания их координаты х. Аналогично;,массив У отсортирован в порядке монотонного возрастания координаты у. Заметим, что достигнуть границы 0 (и!ли) не удастся, если сортировка будет производиться в каждом рекурсивном вызове; если бы мы поступали таким образом, то время работы такого метода определялось бы рекуррентным соотношением Т(п) = = 2Т (и/2) + 0 (и 1к и), решение которого равно Т (и) = 0 (и 1бз п). (Это можно показать с помощью версии основного метода, описанной в упражнении 4.4-2.) Немного позже станет понятно, как с помощью "предварительной сортировки" поддерживать отсортированность, не прибегая к процедуре сортировке в каждом рекурсивном вызове.
В рекурсивном вызове со входными данными Р, Х и У сначала проверяется, выполняется ли условие ~Р~ < 3. Если оно справедливо, то в вызове просто применяется упомянутый выше метод решения "в лоб": сравниваются между собой все (~ з ~) пар точек, и возвращается пара точек, расположенных друг к другу ближе других. Если ~Р~ > 3, то производится рекурсивный вызов в соответствии с описанной ниже парадигмой "разделяй и властвуй". Разделение. Находится вертикальная прямая 1, которая делит множество точек Р на два множества Рл и Рн, таких что ~Рт,Я = ЦР)/21, ~Рн~ = ЦР(/21', все точки множества Рл находятся слева от прямой 1 или на этой прямой, а все точки множества Ри находятся справа от прямой 1 или на этой прямой.
Массив Х разбивается на массивы Хг. и Хи, содержащие точки множеств Рл и Рн соответственно, отсортированные в порядке монотонного возрастания координаты х. Аналогично, массив У разбивается на массивы Ул и Уи, содержащие соответственно точки множеств Рд и Ри, отсортированные в порядке монотонного возрастания координаты у. Покорение. После разбиения множества Р на подмножества Рл и Рн производится два рекурсивных вызова: один для поиска пары ближайших точек в множестве Рл, а другой для поиска пары ближайших точек в множестве Рд.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
