WikiSort.ru - Не сортированное

Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве. В этом алгоритме задача о выпуклой оболочке решается с помощью стека, сформированного из точек-кандидатов. Все точки входного множества заносятся в стек, а потом точки, не являющиеся вершинами выпуклой оболочки, со временем удаляются из него. По завершении работы алгоритма в стеке остаются только вершины оболочки в порядке их обхода против часовой стрелки.

Алгоритм

В качестве входных данных процедуры Graham выступает множество точек Q, где ${\displaystyle |Q|\geqslant 3}$ . В ней вызывается функция Top(S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NextToTop(S), которая возвращает точку, расположенную в стеке S, на одну позицию ниже от верхней точки; стек S при этом не изменяется.

Graham(Q)
1) Пусть ${\displaystyle p_{0}}$
 — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений
2) Пусть ${\displaystyle <p_{1},p_{2},\ldots ,p_{m}>}$
 — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,
      измеряемого против часовой стрелки относительно точки ${\displaystyle p_{0}}$
 
     (если полярные углы нескольких точек совпадают, то по расстоянию до точки ${\displaystyle p_{0}}$
)
3) Push(${\displaystyle p_{0}}$
,S)
4) Push(${\displaystyle p_{1}}$
,S)
5) for i = 2 to m do
6)     while угол, образованный точками NextToTop(S),Top(S) и ${\displaystyle p_{i}}$
, образуют не левый поворот
            (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)
7)       do Pop(S)
8)    Push(${\displaystyle p_{i}}$
,S)
9) return S

Для определения, образуют ли три точки ${\displaystyle a}$ , ${\displaystyle b}$ и ${\displaystyle c}$ левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: ${\displaystyle u_{x}v_{y}-u_{y}v_{x}\geqslant 0}$ , где ${\displaystyle u=\left\{b_{x}-a_{x},\;b_{y}-a_{y}\right\},v=\left\{c_{x}-b_{x},\;c_{y}-b_{y}\right\}}$

• Пример работы алгоритма Грэхема.
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 
• 

Корректность сканирования по Грэхему

Если процедура Graham обрабатывает множество точек Q, где ${\displaystyle |Q|\geqslant 3}$ , то по завершении этой процедуры стек S будет содержать (в направлении снизу вверх) только вершины оболочки CH(Q) в порядке обхода против часовой стрелки.

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

После выполнения строки 2 в нашем распоряжении имеется последовательность точек ${\displaystyle <p_{1},p_{2},\ldots ,p_{m}>}$ . Определим подмножество точек ${\displaystyle Q_{i}=\left\{p_{0},p_{1},\ldots ,p_{i}\right\}}$ при i = 2,3,…,m. Множество точек Q — ${\displaystyle Q_{m}}$ образуют те из них, что были удалены из-за того, что их полярный угол относительно точки p0 совпадает с полярным углом некоторой точки из множества ${\displaystyle Q_{m}}$ . Эти точки не принадлежат выпуклой оболочке CH(Q), так что CH(${\displaystyle Q_{m}}$ ) = CH(Q). Таким образом, достаточно показать, что по завершении процедуры Graham стек S состоит из вершин оболочки CH(${\displaystyle Q_{m}}$ ) в порядке обхода против часовой стрелки, если эти точки просматриваются в стеке снизу вверх. Заметим, что точно так же, как точки ${\displaystyle p_{0}}$ ,${\displaystyle p_{1}}$ ,${\displaystyle p_{m}}$ являются вершинами оболочки CH(Q), точки ${\displaystyle p_{0}}$ ,${\displaystyle p_{1}}$ ,${\displaystyle p_{i}}$ являются вершинами оболочки CH(${\displaystyle Q_{i}}$ ).

В доказательстве используется сформулированный ниже инвариант цикла. В начале каждой итерации цикла for в строках 6-9 стек S состоит(снизу вверх) только из вершин оболочки CH(${\displaystyle Q_{i-1}}$ ) в порядке их обхода против часовой стрелки.

Инициализация. При первом выполнении строки 6 инвариант поддерживается, поскольку в этот момент стек S состоит только из вершин ${\displaystyle Q_{2}}$ = ${\displaystyle Q_{i-1}}$ , и это множество трех вершин формирует свою собственную выпуклую оболочку. Кроме того, если просматривать точки снизу вверх, то они будут расположены в порядке обхода против часовой стрелки.

Сохранение. При входе в новую итерацию цикла for вверху стека S находится точка ${\displaystyle p_{i-1}}$ , помещенная туда в конце предыдущей итерации (или перед первой итерацией, когда i = 3). Пусть ${\displaystyle p_{j}}$  — верхняя точка стека S после выполнения строк 7-8 цикла while, но перед тем, как в строке 9 в стек будет помещена точка ${\displaystyle p_{i}}$ . Пусть также ${\displaystyle p_{k}}$  — точка, расположенная в стеке S непосредственно под точкой ${\displaystyle p_{j}}$ . В тот момент, когда точка ${\displaystyle p_{j}}$ находится наверху стека S, а точка ${\displaystyle p_{i}}$ ещё не добавлена, стек содержит те же точки, что и после j-й итерации цикла for. Поэтому, согласно инварианту цикла, в этот момент стек S содержит только CH(${\displaystyle Q_{j}}$ ) в порядке их обхода против часовой стрелки, если просматривать их снизу вверх. Полярный угол точки ${\displaystyle p_{i}}$ относительно точки ${\displaystyle p_{0}}$ больше, чем полярный угол точки ${\displaystyle p_{j}}$ , и поскольку угол ${\displaystyle p_{k}}$ ${\displaystyle p_{j}}$ ${\displaystyle p_{i}}$ сворачивает влево(в противном случае точка ${\displaystyle p_{j}}$ была бы снята со стека), после добавления в стек S точки ${\displaystyle p_{i}}$ (до этого там были только вершины CH(${\displaystyle Q_{j}}$ )) в нем будут содержаться вершины CH(${\displaystyle Q_{j}\cup \left\{p_{i}\right\}}$ ). При этом они будут расположены в порядке обхода против часовой стрелки, если просматривать их снизу вверх.

Покажем, что множество вершин CH(${\displaystyle Q_{j}\cup \left\{p_{i}\right\}}$ ) совпадает с множеством точек CH(${\displaystyle Q_{i}}$ ). Рассмотрим произвольную точку ${\displaystyle p_{t}}$ , снятую со стека во время выполнения i-й итерации цикла for, и пусть ${\displaystyle p_{r}}$  — точка, расположенная в стеке S непосредственно под точкой ${\displaystyle p_{t}}$ перед снятием со стека последней(этой точкой pr может быть точка ${\displaystyle p_{j}}$ ). Угол ${\displaystyle p_{r}}$ ${\displaystyle p_{t}}$ ${\displaystyle p_{i}}$ не сворачивает влево, и полярный угол точки ${\displaystyle p_{t}}$ относительно точки ${\displaystyle p_{0}}$ больше полярного угла точки ${\displaystyle p_{r}}$ . Так как точка ${\displaystyle p_{t}}$ находится внутри треугольника, образованного тремя другими точками множества ${\displaystyle Q_{i}}$ , она не может быть вершиной CH(${\displaystyle Q_{i}}$ ). Так как ${\displaystyle p_{t}}$ не является вершиной CH(${\displaystyle Q_{i}}$ ), то CH(${\displaystyle Q_{i}}$  — {${\displaystyle p_{t}}$ }) = CH(${\displaystyle Q_{i}}$ ). Пусть ${\displaystyle P_{i}}$  — множество точек, снятых со стека во время выполнения i-ой итерации цикла for. Верно равенство CH(${\displaystyle Q_{i}}$  — ${\displaystyle P_{i}}$ ) = CH(${\displaystyle Q_{i}}$ ). Однако ${\displaystyle Q_{i}}$  — ${\displaystyle P_{i}}$ = ${\displaystyle Q_{i}}$ ${\displaystyle \cup }$ {${\displaystyle p_{i}}$ }, поэтому мы приходим к заключению, что CH(${\displaystyle Q_{j}}$ ${\displaystyle \cup }$ {${\displaystyle p_{i}}$ }) = CH(${\displaystyle Q_{i}}$  — ${\displaystyle P_{i}}$ ) = CH(${\displaystyle Q_{i}}$ ).

Сразу после вытеснения из стека S точки ${\displaystyle p_{i}}$ в нем содержатся только вершины CH(${\displaystyle Q_{i}}$ ) в порядке их обхода против часовой стрелки, если просматривать их в стеке снизу вверх. Последующее увеличение на единицу значения i приведет к сохранению инварианта цикла в очередной итерации.

Завершение. По завершении цикла выполняется равенство i = m + 1, поэтому из инварианта цикла следует, что стек S состоит только из вершин CH(${\displaystyle Q_{m}}$ ), то есть из вершин CH(Q). Эти вершины расположены в порядке обхода против часовой стрелки, если они просматриваются в стеке снизу вверх.

Время работы

Время работы процедуры Graham равно O(n lg n), где n = |Q|. Как несложно показать, циклу while потребуется время O(n). В то время, как сортировка полярных углов займет O(n lg n) времени, откуда и следует общая асимптотика процедуры Graham.

См. также

• Алгоритм Джарвиса
• Алгоритм Чана
• Алгоритм быстрой оболочки
• Алгоритм монотонных цепочек Эндрю

Литература

• Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. Алгоритмы. Построение и анализ = Introduction to Algorithms. — 2-e изд. — “Вильямс”, 2005.

Ссылки

• Визуализатор
• Реализация на c++
• Реализация на Java
• Реализация на Haskell