Русская Википедия:Алгоритм Грэхема
Алгоритм Грэхема — алгоритм построения выпуклой оболочки в двумерном пространстве. В этом алгоритме задача о выпуклой оболочке решается с помощью стека, сформированного из точек-кандидатов. Все точки входного множества заносятся в стек, а потом точки, не являющиеся вершинами выпуклой оболочки, со временем удаляются из него. По завершении работы алгоритма в стеке остаются только вершины оболочки в порядке их обхода против часовой стрелки.
Алгоритм
В качестве входных данных процедуры Graham выступает множество точек Q, где <math>|Q|\geqslant 3</math>. В ней вызывается функция Top(S), которая возвращает точку, находящуюся на вершине стека S, не изменяя при этом его содержимое. Кроме того, используется также функция NextToTop(S), которая возвращает точку, расположенную в стеке S, на одну позицию ниже от верхней точки; стек S при этом не изменяется.
Graham(Q)
1) Пусть <math>p_0</math> — точка из множества Q с минимальной координатой y или самая левая из таких точек при наличии совпадений
2) Пусть <math><p_1, p_2,\ldots,p_m></math> — остальные точки множества Q, отсортированные в порядке возрастания полярного угла,
измеряемого против часовой стрелки относительно точки <math>p_0</math>
(если полярные углы нескольких точек совпадают, то по расстоянию до точки <math>p_0</math>)
3) Push(<math>p_0</math>,S)
4) Push(<math>p_1</math>,S)
5) for i = 2 to m do
6) while угол, образованный точками NextToTop(S),Top(S) и <math>p_i</math>, образуют не левый поворот
(при движении по ломаной, образованной этими точками, мы движемся прямо или вправо)
7) do Pop(S)
8) Push(<math>p_i</math>,S)
9) return S
Для определения, образуют ли три точки <math>a</math>, <math>b</math> и <math>c</math> левый поворот, можно использовать обобщение векторного произведения на двумерное пространство, а именно условие левого поворота будет выглядеть следующим образом: <math>u_x v_y - u_y v_x \geqslant 0</math>, где <math> 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>|Q|\geqslant 3</math>, то по завершении этой процедуры стек S будет содержать (в направлении снизу вверх) только вершины оболочки CH(Q) в порядке обхода против часовой стрелки.
Доказательство
После выполнения строки 2 в нашем распоряжении имеется последовательность точек <math><p_1, p_2,\ldots,p_m></math>. Определим подмножество точек <math>Q_i = \left\{p_0,p_1,\ldots,p_i\right\}</math> при i = 2,3,…,m. Множество точек Q — <math>Q_m</math> образуют те из них, что были удалены из-за того, что их полярный угол относительно точки p0 совпадает с полярным углом некоторой точки из множества <math>Q_m</math>. Эти точки не принадлежат выпуклой оболочке CH(Q), так что CH(<math>Q_m</math>) = CH(Q). Таким образом, достаточно показать, что по завершении процедуры Graham стек S состоит из вершин оболочки CH(<math>Q_m</math>) в порядке обхода против часовой стрелки, если эти точки просматриваются в стеке снизу вверх. Заметим, что точно так же, как точки <math>p_0</math>,<math>p_1</math>,<math>p_m</math> являются вершинами оболочки CH(Q), точки <math>p_0</math>,<math>p_1</math>,<math>p_i</math> являются вершинами оболочки CH(<math>Q_i</math>).
В доказательстве используется сформулированный ниже инвариант цикла. В начале каждой итерации цикла for в строках 6-9 стек S состоит(снизу вверх) только из вершин оболочки CH(<math>Q_{i-1} </math>) в порядке их обхода против часовой стрелки.
Инициализация. При первом выполнении строки 6 инвариант поддерживается, поскольку в этот момент стек S состоит только из вершин <math>Q_2</math> = <math>Q_{i-1} </math>, и это множество трех вершин формирует свою собственную выпуклую оболочку. Кроме того, если просматривать точки снизу вверх, то они будут расположены в порядке обхода против часовой стрелки.
Сохранение. При входе в новую итерацию цикла for вверху стека S находится точка <math>p_{i-1} </math>, помещенная туда в конце предыдущей итерации (или перед первой итерацией, когда i = 3). Пусть <math>p_j</math> — верхняя точка стека S после выполнения строк 7-8 цикла while, но перед тем, как в строке 9 в стек будет помещена точка <math>p_i</math>. Пусть также <math>p_k</math> — точка, расположенная в стеке S непосредственно под точкой <math>p_j</math>. В тот момент, когда точка <math>p_j</math> находится наверху стека S, а точка <math>p_i</math> ещё не добавлена, стек содержит те же точки, что и после j-й итерации цикла for. Поэтому, согласно инварианту цикла, в этот момент стек S содержит только CH(<math>Q_j</math>) в порядке их обхода против часовой стрелки, если просматривать их снизу вверх. Полярный угол точки <math>p_i</math> относительно точки <math>p_0</math> больше, чем полярный угол точки <math>p_j</math>, и поскольку угол <math>p_k</math><math>p_j</math><math>p_i</math> сворачивает влево(в противном случае точка <math>p_j</math> была бы снята со стека), после добавления в стек S точки <math>p_i</math> (до этого там были только вершины CH(<math>Q_j</math>)) в нем будут содержаться вершины CH(<math>Q_j \cup \left\{p_i\right\}</math>). При этом они будут расположены в порядке обхода против часовой стрелки, если просматривать их снизу вверх.
Покажем, что множество вершин CH(<math>Q_j \cup \left\{p_i\right\}</math>) совпадает с множеством точек CH(<math>Q_i</math>). Рассмотрим произвольную точку <math>p_t</math>, снятую со стека во время выполнения i-й итерации цикла for, и пусть <math>p_r</math> — точка, расположенная в стеке S непосредственно под точкой <math>p_t</math> перед снятием со стека последней(этой точкой pr может быть точка <math>p_j</math>). Угол <math>p_r</math><math>p_t</math><math>p_i</math> не сворачивает влево, и полярный угол точки <math>p_t</math> относительно точки <math>p_0</math> больше полярного угла точки <math>p_r</math>. Так как точка <math>p_t</math> находится внутри треугольника, образованного тремя другими точками множества <math>Q_i</math>, она не может быть вершиной CH(<math>Q_i</math>). Так как <math>p_t</math> не является вершиной CH(<math>Q_i</math>), то CH(<math>Q_i</math> — {<math>p_t</math>}) = CH(<math>Q_i</math>). Пусть <math>P_i</math> — множество точек, снятых со стека во время выполнения i-ой итерации цикла for. Верно равенство CH(<math>Q_i</math> — <math>P_i</math>) = CH(<math>Q_i</math>). Однако <math>Q_i</math> — <math>P_i</math> = <math>Q_i</math> <math>\cup</math> {<math>p_i</math>}, поэтому мы приходим к заключению, что CH(<math>Q_j</math> <math>\cup</math> {<math>p_i</math>}) = CH(<math>Q_i</math> — <math>P_i</math>) = CH(<math>Q_i</math>).
Сразу после вытеснения из стека S точки <math>p_i</math> в нем содержатся только вершины CH(<math>Q_i</math>) в порядке их обхода против часовой стрелки, если просматривать их в стеке снизу вверх. Последующее увеличение на единицу значения i приведет к сохранению инварианта цикла в очередной итерации.
Завершение. По завершении цикла выполняется равенство i = m + 1, поэтому из инварианта цикла следует, что стек S состоит только из вершин CH(<math>Q_m</math>), то есть из вершин CH(Q). Эти вершины расположены в порядке обхода против часовой стрелки, если они просматриваются в стеке снизу вверх.
Время работы
Время работы процедуры Graham равно <math>O(N \log N)</math>, где <math>N = |Q|</math>. Как несложно показать, циклу while потребуется время O(<math>N</math>). В то время, как сортировка полярных углов займет <math>O(N \log N)</math> времени, откуда и следует общая асимптотика процедуры Graham.
См. также
Литература
Ссылки
