Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 238
Текст из файла (страница 238)
Как изменится ответ в упр. 33.2.2, если допускается наличие вертикальных отрезков? 33.3. Поиск выпуклой оболочки Выпуклой оболочкой (сопиех Ьц!1) множества точек Я (обозначаегся СН(Я)) называется наименьший выпуклый многоугольник Р, такой, что каждая точка из ь2 находится либо на границе многоугольника Р, либо в его внутренней области. (Точное определение выпуклого многоугольника можно найти в упр.
33.1.5.) Неявно предполагается, что все точки множества 1~ различны и что в нем имеется как минимум три не коллинеарные точки. Интуитивно можно представлять каждую точку множества Я в виде торчащего из доски гвоздя; тогда выпуклая оболочка будет иметь форму, полученную в результате наматывания на гвозди тугой резиновой нити.
Пример множества точек и их выпуклой оболочки приведен на рис. 33.6. В этом разделе будут представлены два алгоритма, позволяющие построить выпуклую оболочку множества, состоящего из и точек. Оба алгоритма выводят вершины выпуклой оболочки в порядке обхода против часовой стрелки. Время работы первого из них, известного как сканирование по Грэхему, равно 0(п )ли). Второй алгоритм, который называется обходом по Джарвису, выполняется за время 0(пл), где Ь вЂ” юличество вершин выпуклой оболочки. Как видно из рис. 33.6, каждая вершина СН(Я) — это точка множества Я. Это свойство используется в обоих алгоритмах. В них принимается решение о том, какие точки из множества Я выступают в роли вершин выпуклой оболочки, а какие следует отбросить.
Вычислить выпуклую оболочку за время 0(п 1к п) можно несколькими методами. И при сканировании по Грэхему, и при обходе по Джарвису использует- 7076 Часть РИ. Избранные тены Рз Р12 Ро Ряс. 33.6. Множество точек с2 = [ро, рз,..., рзз) н его вылунвев оболочка СН(Я). ся метод, который называется "вымегание по кругу". Вершины обрабатываются в порядке возрастания их полярных углов, юторые они образуют с некоторой базисной вершиной. В число других методов входят те, которые перечислены ниже. ° В инкрементнаи мезподе (1псгешепга( шебзод) точки сначала сортируются слева направо, в результате чего получается последовательность (рм рз,..., р„).
На з-м этапе выпуклая оболочка з — 1 крайних слева точек СН((ры рз,..., р, 1)) обновляется в соответствии с положением з'-й слева точки, формируя, таким образом, оболочку СН((рм рз,..., р,)). В упр. 33.3.б предлагается показать, как реализовать этот метод так, чтобы время его работы было равно 0(п !к п). В методе декомпозиции (бечЫе-аль(-сопс)цег шебзоб) множество п точек за время Н(п) разбивается на два подмножества, в одном из которых содержится (п/2) крайних слева точек, а во втором — 1п/2! крайних справа. Затем рекурсивно вычисляются выпуклые оболочки этих подмножеств, которые впоследствии объединяются с помощью одного остроумного метода за время 0(п).
Время работы этого метода описывается знакомым рекуррентным соотношением Т(п) = 2Т(п/2) + 0(п) „решение которого дает время работы 0(п !я п). Метод отсечения и поиска (рпзпе-алб-зеагсЬ шейзоб) подобен алгоритму, описанному в разделе 9.3, время работы которого в наихудшем случае ведет себя линейно.
В нем строится верхняя часть (или "верхняя цепь") выпуклой оболочки путем многократного отбрасывания фиксированной части оставшихся точек до тех пор, пока не останется толью верхняя цень выпуклой оболочки. Затем то же самое выполняется с нижней цепью. В асимптотическом пределе этот метод самый быстрый: если выпуклая оболочка содержит (з вершин, время его работы равно 0(п )я 7ь). Вычисление выпуклой оболочки множества точек — задача, интересная сама по себе. Кроме того, алгоритмы, предназначенные для решения некоторых других задач вычислительной геометрии„начинают работу с построения выпуклой оболочки.
Например, рассмотрим двумерную задачу о поиске пары самых дальних зпочек (Гаплезыра1г ргоЫеш): в заданном на плоскости множестве п точек требуется найти две, расстояние между которыми является максимальным. В упр. 33.3.3 предлагается доказать, что обе эти точки должны быть вершинами !077 Глава 33. Вычислительная геамеырия выпуклой оболочки. Хотя здесь мы и не станем доказывать это утверждение, пару самых дальних вершин выпуклого п-угольника можно найти в течение времени 0(п). Таким образом, путем построения выпуклой оболочки для и входных точек за время 0(п 18 п) и последующего поиска пары самых дальних точек среди вершин полученною в результате выпуклого многоугольника можно найти пару самых дальних точек из произвольного множества и точек за время 0(п!8 п). Сканирование по Грэхему В методе сканирования по Грэхему (бгаЬаш'з зсап) задача о выпуклой оболочке решается с помощью стека Я, сформированного из точек-кандидатов.
Все точки входного множества по одной Я заносятся в стек, а затем точки, не являющиеся вершинами СН(Я), со временем удаляются из него. По завершении работы алгоритма в стеке Я остаются только вершины оболочки СН(Я) в порядке их обхода против часовой стрелки. В качестве входных данных процедуры бкАнАМ-8сАы выступает множество точек О, где )Я! ) 3. В ней вызывается функция ТОВ(о), которая возвращает точку, находящуюся на вершине стека Я, не изменяя при этом его содержимое. Кроме того, используется также функция 1ч1вхт-То-Тор(Я), которая возвращает точку, расположенную в стеке Я на одну позицию ниже от верхней точки; стек Я при этом не изменяется.
Вскоре будет показано, что стек Я, возвращаемый процедурой ПкАнАМ-БсАн, содержит только вершины СН(Я), причем расположенные в порядке обхода против часовой стрелки, если просматривать их в стеке снизу вверх. глКАНАМ-ЯСАХ((е) 1 Пусть ро — точка 1ь7 с минимальной координатой у, или крайняя слева из таких точек при наличии совпадений 2 Пусть (рм рз,..., р ) — остальные точки Я, отсортированные в порядке возрастания полярного угла, измеряемого против часовой стрелки относительно ро (если полярные углы нескольких точек совпадают, то из множества удаляются все эти точки, кроме одной, самой дальней от точки ро) 3 Н' пь ( 2 4 ге1нгп "выпуклая оболочка пуста" 5 е1яе пусть о — пустой стек 6 Р!3зн(ро, Я) 7 Р17зн(Р„Я) 8 Р13зн(рз, Я) 9 Твг 1 = 3 1о т 10 эгЬИе угол, образованный точками 1ч1пхт-То-Тор(о), Тор(о) и р, не образует поворот влево Рог(Я) РГЗЗН(р,, о) ге1пгп Я Часть р)й ИзбРанные таз, Рю Рю' Р11 Рб Рз Рб Рв Рз .
'Рз РП Рб Р, Рб Рв Р! Р12 Р12 Рз Ро (ь) (6) Рю ° Р1о ° Р11 Рв Рз 'Рв ' Рз Р1! Рб Р) Рб Р! 2 ° Рз Рю' Рз Ро (б) Ро Р10 Р10 Рб Рб Рю Рз Р12 Рэ Ро Ов) Рис. 33.7. Выл Ро ЬЮОЛНЕЮ1Е ПРОЦЕ Ь! - Ы ДЛЯ (б) ып дуры Оилнлм-Бслм для нтераци рь рз,...,, нумерованных а порядке ом шаге, и цикла !ог а возрастания п приводят ктирные линии показ строках 9 — 12.
Пун Ро Р1 и Рз. (6)-(л) С тек Я после кикд олярного к снятию со ек со стека. В части з, показывают поло кикдой роты не влево, е рврзрб приводит к снятию к снятию со Гпааа 33. а Вычислиигльиая гсамсирия Р1о ' Ри Рб РБ Рэ Рэ Р12 Р)2 Ро Ро (и) Рэ Рэ Р(2 Рп' Ро (л) Ро (л) Рэ Ри Р12 (л) Рис. 33.7 (и еделие Ро роиелиенис).
(и) В в (и) анной на рнс 33 6 врицаомая проис)цдэой и и совпадиоп(ая с по- 1ОВО Часть П1. Избранные темы Работа процедуры Оклнлм-Бсл14 проиллюстрирована на рис.33.7. Выпуклая оболочка, содержащаяся на данный момент в стеке Я, на каждом этапе показана серым цветом. В строке 1 процедуры выбирается точка ро с минимальной координатой у; при наличии нескольких таких точек выбирается крайняя слева.
Поскольку в множестве Я отсутствуют точки, расположенные ниже точки ро, а все другие точки с такой же координатой у расположены справа от точки ро, точка рс должна быть вершиной оболочки СН(Я). В строке 2 остальные точки множества Я сортируются в порядке возрастания их полярных углов относительно точки рс. При этом используется тот же метод, что и в упр. 33.1.3, т.е. сравнение векторных произведений. Если полярные углы двух илн нескольких точек относительно точки ро совпадают, все такие точки, кроме самой удаленной от точки ро, являются выпуклыми комбинациями точки ро и самой удаленной от нее из числа таких точек, поэтому все они могут быть исключены из рассмотрения.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
