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

Содержание

• 1 Алгоритм
• 2 Корректность сканирования по Грэхему
• 3 Доказательство
• 4 Время работы
• 5 См. также
• 6 Литература
• 7 Ссылки

Алгоритм

В качестве входных данных процедуры Graham выступает множество точек Q, где . В ней вызывается функция Top(S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NextToTop(S), которая возвращает точку, расположенную в стеке S, на одну позицию ниже от верхней точки; стек S при этом не изменяется.
Graham(Q) 1) Пусть — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений 2) Пусть — остальные точки множества Q, отсортированные в порядке возрастания полярного угла, измеряемого против часовой стрелки относительно точки (если полярные углы нескольких точек совпадают, то по расстоянию до точки ) 3) Push(,S) 4) Push(,S) 5)
for i = 2
to m
do 6)
while угол, образованный точками NextToTop(S),Top(S) и , образуют не левый поворот (при движении по ломаной, образованной этими точками, мы движемся прямо или вправо) 7)
do Pop(S) 8) Push(,S) 9)
return S

Для определения, образуют ли три точки , и левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: , где

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

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

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

После выполнения строки 2 в нашем распоряжении имеется последовательность точек . Определим подмножество точек при i = 2,3,,m. Множество точек Q— образуют те из них, что были удалены из-за того, что их полярный угол относительно точки p0 совпадает с полярным углом некоторой точки из множества . Эти точки не принадлежат выпуклой оболочке CH(Q), так что CH() = CH(Q). Таким образом, достаточно показать, что по завершении процедуры Graham стек S состоит из вершин оболочки CH() в порядке обхода против часовой стрелки, если эти точки просматриваются в стеке снизу вверх. Заметим, что точно так же, как точки ,, являются вершинами оболочки CH(Q), точки ,, являются вершинами оболочки CH().

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

Инициализация. При первом выполнении строки 6 инвариант поддерживается, поскольку в этот момент стек S состоит только из вершин = , и это множество трех вершин формирует свою собственную выпуклую оболочку. Кроме того, если просматривать точки снизу вверх, то они будут расположены в порядке обхода против часовой стрелки.

Сохранение. При входе в новую итерацию цикла for вверху стека S находится точка , помещенная туда в конце предыдущей итерации (или перед первой итерацией, когда i = 3). Пусть — верхняя точка стека S после выполнения строк 7-8 цикла while, но перед тем, как в строке 9 в стек будет помещена точка . Пусть также — точка, расположенная в стеке S непосредственно под точкой . В тот момент, когда точка находится наверху стека S, а точка ещё не добавлена, стек содержит те же точки, что и после j-й итерации цикла for. Поэтому, согласно инварианту цикла, в этот момент стек S содержит только CH() в порядке их обхода против часовой стрелки, если просматривать их снизу вверх. Полярный угол точки относительно точки больше, чем полярный угол точки , и поскольку угол сворачивает влево(в противном случае точка была бы снята со стека), после добавления в стек S точки (до этого там были только вершины CH()) в нем будут содержаться вершины CH(). При этом они будут расположены в порядке обхода против часовой стрелки, если просматривать их снизу вверх.

Покажем, что множество вершин CH() совпадает с множеством точек CH(). Рассмотрим произвольную точку , снятую со стека во время выполнения i-й итерации цикла for, и пусть — точка, расположенная в стеке S непосредственно под точкой перед снятием со стека последней(этой точкой pr может быть точка ). Угол не сворачивает влево, и полярный угол точки относительно точки больше полярного угла точки . Так как точка находится внутри треугольника, образованного тремя другими точками множества , она не может быть вершиной CH(). Так как не является вершиной CH(), то CH(— ) = CH(). Пусть — множество точек, снятых со стека во время выполнения i-ой итерации цикла for. Верно равенство CH(— ) = CH(). Однако — = , поэтому мы приходим к заключению, что CH( ) = CH(— ) = CH().

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

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

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

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

Литература

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

https://ru.wikipedia.org/wiki/Алгоритм_Грэхема