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