Алгоритм Грэхема

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

Алгоритм

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

Graham(Q)
1) Пусть [math]\displaystyle{ p_0 }[/math] — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений
2) Пусть [math]\displaystyle{ \lt p_1, p_2,\ldots,p_m\gt  }[/math] — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,
      измеряемого против часовой стрелки относительно точки [math]\displaystyle{ p_0 }[/math] 
     (если полярные углы нескольких точек совпадают, то по расстоянию до точки [math]\displaystyle{ p_0 }[/math])
3) Push([math]\displaystyle{ p_0 }[/math],S)
4) Push([math]\displaystyle{ p_1 }[/math],S)
5) for i = 2 to m do
6)     while угол, образованный точками NextToTop(S),Top(S) и [math]\displaystyle{ p_i }[/math], образуют не левый поворот
            (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)
7)       do Pop(S)
8)    Push([math]\displaystyle{ p_i }[/math],S)
9) return S

Для определения, образуют ли три точки [math]\displaystyle{ a }[/math], [math]\displaystyle{ b }[/math] и [math]\displaystyle{ c }[/math] левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: [math]\displaystyle{ u_x v_y - u_y v_x \geqslant 0 }[/math], где [math]\displaystyle{ u = \left\{ b_x - a_x, \; b_y - a_y \right\}, v = \left\{ c_x - b_x, \; c_y - b_y \right\} }[/math]

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

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

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

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

После выполнения строки 2 в нашем распоряжении имеется последовательность точек [math]\displaystyle{ \lt p_1, p_2,\ldots,p_m\gt }[/math]. Определим подмножество точек [math]\displaystyle{ Q_i = \left\{p_0,p_1,\ldots,p_i\right\} }[/math] при i = 2,3,…,m. Множество точек Q — [math]\displaystyle{ Q_m }[/math] образуют те из них, что были удалены из-за того, что их полярный угол относительно точки p0 совпадает с полярным углом некоторой точки из множества [math]\displaystyle{ Q_m }[/math]. Эти точки не принадлежат выпуклой оболочке CH(Q), так что CH([math]\displaystyle{ Q_m }[/math]) = CH(Q). Таким образом, достаточно показать, что по завершении процедуры Graham стек S состоит из вершин оболочки CH([math]\displaystyle{ Q_m }[/math]) в порядке обхода против часовой стрелки, если эти точки просматриваются в стеке снизу вверх. Заметим, что точно так же, как точки [math]\displaystyle{ p_0 }[/math],[math]\displaystyle{ p_1 }[/math],[math]\displaystyle{ p_m }[/math] являются вершинами оболочки CH(Q), точки [math]\displaystyle{ p_0 }[/math],[math]\displaystyle{ p_1 }[/math],[math]\displaystyle{ p_i }[/math] являются вершинами оболочки CH([math]\displaystyle{ Q_i }[/math]).

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

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

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

Покажем, что множество вершин CH([math]\displaystyle{ Q_j \cup \left\{p_i\right\} }[/math]) совпадает с множеством точек CH([math]\displaystyle{ Q_i }[/math]). Рассмотрим произвольную точку [math]\displaystyle{ p_t }[/math], снятую со стека во время выполнения i-й итерации цикла for, и пусть [math]\displaystyle{ p_r }[/math] — точка, расположенная в стеке S непосредственно под точкой [math]\displaystyle{ p_t }[/math] перед снятием со стека последней(этой точкой pr может быть точка [math]\displaystyle{ p_j }[/math]). Угол [math]\displaystyle{ p_r }[/math][math]\displaystyle{ p_t }[/math][math]\displaystyle{ p_i }[/math] не сворачивает влево, и полярный угол точки [math]\displaystyle{ p_t }[/math] относительно точки [math]\displaystyle{ p_0 }[/math] больше полярного угла точки [math]\displaystyle{ p_r }[/math]. Так как точка [math]\displaystyle{ p_t }[/math] находится внутри треугольника, образованного тремя другими точками множества [math]\displaystyle{ Q_i }[/math], она не может быть вершиной CH([math]\displaystyle{ Q_i }[/math]). Так как [math]\displaystyle{ p_t }[/math] не является вершиной CH([math]\displaystyle{ Q_i }[/math]), то CH([math]\displaystyle{ Q_i }[/math] — {[math]\displaystyle{ p_t }[/math]}) = CH([math]\displaystyle{ Q_i }[/math]). Пусть [math]\displaystyle{ P_i }[/math] — множество точек, снятых со стека во время выполнения i-ой итерации цикла for. Верно равенство CH([math]\displaystyle{ Q_i }[/math] — [math]\displaystyle{ P_i }[/math]) = CH([math]\displaystyle{ Q_i }[/math]). Однако [math]\displaystyle{ Q_i }[/math] — [math]\displaystyle{ P_i }[/math] = [math]\displaystyle{ Q_i }[/math] [math]\displaystyle{ \cup }[/math] {[math]\displaystyle{ p_i }[/math]}, поэтому мы приходим к заключению, что CH([math]\displaystyle{ Q_j }[/math] [math]\displaystyle{ \cup }[/math] {[math]\displaystyle{ p_i }[/math]}) = CH([math]\displaystyle{ Q_i }[/math] — [math]\displaystyle{ P_i }[/math]) = CH([math]\displaystyle{ Q_i }[/math]).

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

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

Время работы

Время работы процедуры Graham равно [math]\displaystyle{ O(N \log N) }[/math], где [math]\displaystyle{ N = |Q| }[/math]. Как несложно показать, циклу while потребуется время O([math]\displaystyle{ N }[/math]). В то время, как сортировка полярных углов займет [math]\displaystyle{ O(N \log N) }[/math] времени, откуда и следует общая асимптотика процедуры Graham.

См. также

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

Литература

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

Ссылки

• Реализация на c++
• Реализация на Java
• Реализация на Haskell