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

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

АлгоритмПравить

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

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

Для определения, образуют ли три точки $a$$a$ , $b$$b$  и $c$$c$  левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: $u_x{v}_y-<!--\; -\; -->u_y{v}_x⩾<!--\; ⩾\; -->0$$u_{x}v_{y}-u_{y}v_{x}\geqslant 0$ , где $u=\left\{b_x-<!--\; -\; -->a_x,b_y-<!--\; -\; -->a_y\right\},v=\left\{c_x-<!--\; -\; -->b_x,c_y-<!--\; -\; -->b_y\right\}$$u=\left\{b_{x}-a_{x},\;b_{y}-a_{y}\right\},v=\left\{c_{x}-b_{x},\;c_{y}-b_{y}\right\}$ 

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

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

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

ДоказательствоПравить

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

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

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

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

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

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

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

Время работыПравить

Время работы процедуры Graham равно $O(N\log <!--\; \; -->N)$$O(N\log N)$ , где $N=|Q|$$N=|Q|$ . Как несложно показать, циклу while потребуется время O($N$$N$ ). В то время, как сортировка полярных углов займет $O(N\log <!--\; \; -->N)$$O(N\log N)$  времени, откуда и следует общая асимптотика процедуры Graham.

См. такжеПравить

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

ЛитератураПравить

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

СсылкиПравить

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