Graham-Scan(Q)

1пусть $р 0$ --- точка из множества $Q$ с наименьшей ординатой

(если таковых несколько --- самая левая)

2пусть $\langle р 1, р 2, ... p m \rangle$ --- остальные точки

множества $Q$, отсортированные в порядке возрастания полярного угла (против часовой стрелки) относительно точки $р 0$ Если есть несколько точек с одинаковым полярным углом, то оставляем только самую удал\"~~а5нную от $р 0$.

3сделать стек $S$ пустым

4$Push(S,p 0)$

5$Push(S,p l)$

6$Push(S,p 2)$

7\emph{for} $i\leftarrow 3 \emph{to} m$

8\emph{do while} при движении по ломаной

$Iext-To-Top(S) \rightarrow Top(S) \rightarrow p мы двигаемся прямо или направо

9\emph{do} $Pop(S)$

10$Push(S,p i)$

11\emph{return} $S$

На рисунке 35.7 показаны шаги выполнения алгоритма Graham-Scan. В строке 1 мы находим точку ро; все остальные точки множества Q находятся выше неё (или на одном уровне, но правее), и потому она заведомо ю входит в CH(Q). В строке 2 оставшиеся точки множества Q упорядочиваются полярному углу относительно точки ро- Каждое сравнение можно выполнить за время 0(1) с помощью произведений (упр. 35.1-2); из точек с одинаковым углом остаётся самая дальняя (остальные заведомо не принадлежат выпуклой оболочке). Полярный углы точек множества Q находятся в пределах промежутка [0, тг). Заметим, что точки pi и рт являются вершинами CH(Q) (упр. 35.3-1).

Затем (строки 3-6) мы помещаем в стек три первые точки Po,pi,P2, после чего можем утверждать, что стек содержит выпуклую оболочку множества po,Pi, • • • ,Pk ПРИ к = 2. Это свойство будет поддерживаться и в дальнейшем, а к будет расти, пока не станет равным то. При движении от дна стека к его вершине мы всё время поворачиваем налево. Если просто так добавить очередную точку в стек, мы нарушим это свойство, поэтому предварительно мы выбрасываем несколько верхних вершин стека.

Теорема 35.2 (алгоритм Грэхема правилен)

После исполнения процедуры Graham-Scan для множества точек Q, содержащего по меньшей мере три точки, в стеке S содержится выпуклая оболочка множества Q (в порядке обхода против часовой стрелки).

Доказательство.

По-настоящему строгое доказательство выходит за рамки книги

рисунок совпадает с 35.8 (Ь), только нет точки рг-, пунктирных линий poPiPj и серой области

35.8Если точки pi, ,Pk,Pj идут в порядке возрастания полярных углов (относительно точки ро), которые меняются в промежутке от [О, тг), и при движении по ломаной poPi • • -PkPj мы в каждой вершине поворачиваем налево, то выпуклой оболочкой точек ро, р\, , РкЛН будет многоугольник, вершинами которого будут все эти точки, а границей будет ломаная poPi • • -PkPjPo

[рисунок совпадает с 35.8 (а), только добавлено обозначение р\ для точки рядом с ро]

35.9Если точки р\,... ,Pk,Pj,Pi идут в порядке возрастания полярных углов (относительно точки ро), которые меняются в промежутке от [0, тг), и при движении по двум соседним участкам PkPjPi ломаной poPi • • - PkPjPi мы поворачиваем вправо или идём прямо, то выпуклая оболочка точек pi,... ,pk,Pj,Pi не изменится после удаления точки pj (поскольку она лежит внутри треугольника poPkPi)-

(строгое определение внутренности многоугольника- уже непростая задача), поэтому мы лишь укажем два наглядно очевидных факта, которые гарантируют правильность алгоритма; они показаны на рис. 35.8 и 35.9

ВНИМАНИЕ: ЗДЕСЬ НОВЫЕ РИСУНКИ!!!

Покажем теперь, что время работы алгоритма Graham-Scan есть О (га lgra), где га = \Q\. Сортировка укладывается в эти границы, если использовать сортировку слиянием или с помощью кучи. Остальная часть алгоритма требует времени О (га). Это не сразу очевидно, поскольку очередная итерация цикла for, помимо добавления одной новой точки, может потребовать удаления нескольких (и, возможно, многих) старых.

Тем не менее, методы амортизационного анализа позволяют легко доказать, что общее число действий есть О (га). В самом деле, любая точка рг- добавляется в стек S только один раз, а потому и удаляется не более одного раза. Тем самым общее время и на добавление, и на удаление есть О (га). (Аналогичное рассуждение мы использовали в разделе 18.1 при анализе процедуры Multipop.)

Проход Джарвиса

Проход Джарвиса вычисляет выпуклую оболочку множества точек Q при помощи «заворачивания» (package wrapping, gift wrapping). Алгоритм требует времени O(nh), где h - число вершин выпуклой оболочки. Поэтому, для класса задач, где h есть o(lgra), проход Джарвиса асимптотически быстрее просмотра Грэхема.

Идея алгоритма такова: мы хотим обвязать наши гвозди верёвкой. Конец верёвки прикрепим к нижнему гвоздю ро (которая выбирается как и в предыдущем алгоритме), и пустим верёвку вправо. Затем будем поднимать правый конец верёвки,

пока она не коснётся некоторого гвоздя р\. Дальше мы вращаем верёвку уже относительно pi, пока она не коснётся следуюёщего гвоздя р2- Так продолжается, пока верёвка не дойдёт до исходной точки ро-

Более формально, последовательность точек Н = (po,pi,... ,Ph~ 1), являющихся вершинами CH(Q), строится так. Мы начинаем с точки ро. Следующая точка р\ имеет наименьший (среди всех точек множества Q) полярный угол относительно ро (см. рис. 35.10) (Если таковых несколько, выбираем самую далёкую.) Затем мы, стоя в точке pi, сравниваем полярные углы всех точек и выбираем точку р2 с наименьшим полярным углом (относительно pi), и так далее. В какой-то момент мы дойдём до верхней точки (точки с наибольшей ординатой), после чего процесс продолжится, только теперь надо отсчитывать полярные углы от луча, направленного влево, а не вправо. Тем самым мы построим сначала (до верхней точки) правую цепь (right chain) выпуклой оболочки, а затем левую цепь (рис. 35.10)

На самом деле можно было бы обойтись без выделения правой и левой цепи. Для этого можно обычно хранить направление последней найденной стороны и выбирать точку с ближайшим (в положительную сторону) направлением луча. Впрочем, в этом случае несколько сложнее сравнивать углы (при использовании левой и правой цепи сравнение углов можно произвести с помощью приёмов раздела 35.1, не вычисляя их явно.

При естественной реализации проход Джарвиса выполняется за время O(nh). Для каждой вершины h выпуклой оболочки CH(Q) мы ищем вершину с минимальным полярным углом. Каждое сравнение углов выполняется за время 0(1) (при этом можно обойтись без тригонометрии, использовав приёмы разд. 35.1), так что поиск минимума требует времени 0(п) (разд. 10.1). Общее время, будет, таким образом, О(nh).

Упражнения

35.3-1

Докажите, что точки р\ и рт в процедуре Graham-Scan окажутся вершинами CH(Q). 35.3-2

Будем считать, что сложение, умножение и сравнение выполняются за время 0(1). Покажите, что если мы умеем находить выпуклую оболочку п точек (вершины которой требуется указать в порядке обхода против часовой стрелки) быстрее чем за (га lgra) шагов, то можно отсортировать п чисел быстрее чем за fi(ralgra) шагов.

35.3-3

В множестве точек Q возьмём две наиболее удалённые друг от друга точки. Покажите, что обе они являются вершинами выпуклой оболочки.