Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 240
Текст из файла (страница 240)
По крайней мере три точки (ро, р1 и р ) никогда не снимаются со стека, поэтому всего выполняется не более т — 2 операций Рог. В каждой итерации цикла зеЫ1е выполняется одна операция Рог, следовательно, всего этих итераций не более т — 2. Так как проверка в строке !О занимает время 0(1), каждый вызов Рог требует времени 0(1), и т < и — 1, полное время, которое требуется для выполнения цикла ьеЫ)е, равно 0(и). Таким образом, время выполнения процедуры Оклнлм-Ясли составляет 0(и 1я и). Обход по Джарвису При построении выпуклой оболочки множества точек Я путем обхода по Джарвису (1аги!з'з шагсЬ) используется метод, известный как упаковка пакеава (расйаяе жгарршй) или упаковка подарка (я!й ьигарр!пя).
Время выполнения алгоритма равно 0(ий), где 6 — количество вершин СН(()). В том случае, когда 6 равно о(!я и), обход по Джарвису работает быстрее, чем сканирование по Грэхему. Интуитивно обход по Джарвису моделирует обертыванне плотного куска бумаги вокруг множества !ь7. Начнем с того, что прикрепим конец бумаги к самой низкой точке множества, т.е. к той же точке ро, с которой начинается сканирование по Грэхему.
Эта точка является вершиной выпуклой оболочки. Натянем бумагу вправо, чтобы она не провисала, после чего будем перемещать ее вверх до тех пор, пока она не коснется какой-либо точки. Эта точка также должна быть убвл Часть РИ Иэбропные тецм Лева» цепь, Права» цепь — — ь Левая цепь ' Правая цепь Рис. 333Х Обход по Джарвису. В качестве первой вершины выбирается иаиниэшвя точка ра Следующая вершина, рь имеет наименьший полярный угол по отношению к ро среди всех точек. Затем точка ра имеет наименьший полярный угол по отношению к рь Правая цепь идет вверх до самой верхней точки ра Затем выполняегса построение левой цепи путем поиска наименьших полярных углов относительно отрицательного направления оси к.
вершиной выпуклой оболочки. Сохраняя бумагу натянутой, продолжим наматывать ее на множество вершин, пока не вернемся к исходной точке ро. Если говорить более формально, то при обходе по Джарвису строится последовательность Н = (ро, рг,..., рь 1) вершин СНЯ). Начнем с точки ро. Как видно из рис. 33.9, следующая вершина выпуклой оболочки рг имеет наименьший полярный угол относительно точки ро. (При наличии совпадений выбирается точка, наиболее удаленная от точки ро.) Аналогично точка рз имеет наименьший полярный угол относительно точки рг и т.д.
По достижении самой высокой вершины, скажем, рь (совпадения разрешаются путем выбора самой удаленной из таких вершин), оказывается построенной (рис. 33.9) правая цепь (пйМ сйа(п) оболочки СН(О). Чтобы сконструировать левую цепь (!ей сЬаш), начнем с точки рь и выберем в качестве рь+1 точку с наименьшим полярным углом относительно точки рь, но относительно отрицательного направления оси х.
Продолжаем выполнять эту процедуру, отсчитывая полярный угол от отрицательного направления оси х, пока не вернемся к исходной точке ро. Обход по Джарвису можно было бы реализовать путем единообразного обхода вокруг выпуклой оболочки, т.е. не прибегая к отдельному построению правой н левой цепей. В такой реализации обычно отслеживается угол последней стороны выпуклой оболочки и накладывается требование, чтобы последовательность углов, образованных сторонами оболочки с положительным направлением оси х, строго возрастала (в интервале от 0 до 2я радиан).
Преимущество конструирования отдельных цепей заключается в том, что исключается необходимость !085 Глава 33. Вычислитлллнал геачлнрил явно вычислять углы; достаточно сравнения углов методами, описанными в разделе 33.1. При надлежащей реализации время выполнения обхода по Джарвису равно 0(иЬ). Для каждой из й вершин оболочки СНЯ) выполняется поиск вершины с минимальным полярным углом. Каждое сравнение полярных углов выполняется за время 0(1), если использовать методы, описанные в разделе 33.1. Как показано в разделе 9.1, если каждая операция сравнения выполняется за время 0(1), то выбор минимального из и значений занимает время 0(и).
Таким образом, обход по Джарвису завершается за время 0(ии). Упражнения 33.3.3 Докажите, что в процедуре ОкАнлм-беям точки рг и р должны быть вершинами СН(Я). Рассмотрим модель вычислений, которая поддерживает сложение, сравнение и умножение и в которой существует нижняя граница времени сортировки и чисел, равная Й(и!и и). Докажите, что в такой модели П(и 1я и) — нижняя граница времени вычисления вершин выпуклой оболочки множества и точек в порядке их обхода. 33.3.3 Докажите, что в заданном множестве точек Я две самые удаленные одна от другой точки должны быть вершинами СН(Я). Для заданного многоугольника Р и точки о на его границе тенью (з!лаболч) точки о называется множество точек г, для которых отрезок дг полностью находится на границе или во внутренней области многоугольника Р.
Как показано на рис. 33.10, многоугольник Р является звездообразным (згаг-зЬаред), если в его внутренней области существует точка р, которая находится в тени любой точки, лежащей на границе зтого многоугольника. Множество всех таких точек называется ядран (кегле!) многоугольника Р. Пусть звездообразный и-угольник Р задан своими вершинами, перечисленными в порядке обхода против часовой стрелки.
Покажите, как построить СН(Р) за время 0(и). 33.3.5 В оперативной задаче о вмпуклой оболочке (оп-1ше сопчех4ш11 ргоЫеш) параметры каждой из и точек из заданного множества Я становятся известными по одной точке за раз. После получения сведений об очередной точке строится выпуклая оболочка тех точек, о которых стало известно к настоящему времени.
Очевидно, можно было бы применять сканирование по Грэхему к каждой из точек, затратив при зтом полное время, равное 0(и !я и). Покажите, как решить оперативную задачу о выпуклой оболочке за время 0(из). )ббб Часть Ий Избранные темы (6) (а) Рнс. 33дй. Определение звездообразного мноп)угольника, о котором идет речь в упр.
33.3зй (а) Звездообразный многоугольник. Отрезок, соединяюший точку р с любой нз приналдежашик границе многоугольника точек О, пересекает зту границу только в точке а (6) Многоугольник, не явлтогдийсл звездообразным. неявленная серым цветом левал область являетсв тенью точки а а выделенная правая область — тенью точки д'.
Поскольку зти области не перекрываютса, ядро явлаеюя пустым. ЗЗ.З.б * Покажите, как реализовать инкрементный метод построения выпуклой оболочки и точек таким образом, чтобы время его работы было равно 0(п 1к и). 33.4. Поиск пары блигкайших точек Теперь рассмотрим задачу о поиске в множестве ф состоящем из и > 2 точек, пары точек, ближайших одна к другой. Термин "ближайший*' относится к обычному евклидову расстоянию: расстояние между точками р) — — (хт, у)) 11 Рг = (хг Уг) Равно (х) — хг) + (У) — Уг) Лве точки множества Я могУт совпадать; в этом случае расстояние между ними равно нулю. Эта задача находит применение, например, в системах управления движением транспорта.
В системе управления воздушным или морским транспортом может понадобиться узнать, какие из двух транспортных средств находятся друг к другу ближе всего, чтобы предотвратить возможное столкновение между ними. В алгоритме, работающем "в лоб", просто перебираются все (") = тз(пг) пар точек. В данном разделе описывается решение этой задачи с помощью алгоритма разбиения ("разделяй и властвуй" ). Время решения этим методом определяется знакомым рекуррентным соотношением Т(п) = 2Т(п/2) + 0(п). Таким образом, время работы этого алгоритма равно 0(гг 1й и). Алгоритм декомпозиции В каждом рекурсивном вызове описываемого алгоритма в качестве входных данных используются подмножество Р С Я и массивы Х и У, в каждом из которых содержатся все точки входного подмножества Р.
Точки в массиве Х отсортированы в порядке возрастания их координаты х. Аналогично массив У отсортирован в порядке возрастания координаты у. Заметим, что достигнуть границы 0(п 1к и) не удастся, если сортировка будет выполняться в каждом рекурсивном 7007 Глава ЗЗ. Вычислитечьиал гевнетрил вызове; если бы мы поступали таким образом, то время работы такого метода определялось бы рекуррентным соотношением Т(п) = 2Т(п/2) + О(п 1к п), решение которого равно Т(п) = 0(п 1й~ и). (Это можно показать с помощью версии основного метода, описанной в упр. 4.6.2.) Немного позже станет понятно, как с помощью "предварительной сортировки" поддерживать свойство отсортированности, ие прибегая к процедуре сортировки в каждом рекурсивном вызове.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
