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

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

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

Graham(Q)

1) Пусть p0 — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений

2) Пусть — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,

измеряемого против часовой стрелки относительно точки p0

(если полярные углы нескольких точек совпадают, то по расстоянию до точки p0)

3) Push(p0,S)

4) Push(p1,S)

5) for i = 2 to m do

6) while угол, образованный точками NextToTop(S),Top(S) и pi, образуют не левый поворот

(при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)

7) do Pop(S)

8) Push(pi,S)

9) return S

Для определения, образуют ли три точки a, b и c левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: uxvy − uyvx > 0, где 

• Пример работы А.Г.:

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

   

• 

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

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