Algorytm Grahama  rozwiązywania problemu otoczki, znajduje nie tylko zbiór wierzchołków wielokąta tworzącego otoczkę, ale także podaje kolejność, w jakiej te wierzchołki występują na obwodzie wielokąta.

Metoda zastosowana w algorytmie korzysta z trzech obserwacji:

1. punkt p[0], który ma najmniejszą współrzędną y (leżący najniżej), a jeżeli jest ich wiele to taki, który dodatkowo ma najmniejszą współrzędną x, musi być wierzchołkiem otoczki wypukłej,
2. jeśli uporządkujemy wszystkie punkty ze względu na kąt jaki tworzy  wektor  p[0],p  z dodatnim kierunkiem osi OX, to kolejność wybierania wierzchołków będzie odpowiadała ich kolejności na obwodzie budowanego wielokąta,
3. jeśli mamy już zbudowaną otoczkę wypukłą zbioru Q, to wszystkie pozostałe punkty zbioru Q leżą po lewej stronie każdej krawędzi otoczki, jeśli przesuwamy się po niej w kierunku przeciwnym do ruchu wskazówek zegara.

W metodzie Grahama, otoczkę budujemy metodą kolejnych prób, rezygnując ewentualnie z wcześniej wybranych punktów, jeśli okaże się, że nie mogą one być wierzchołkami otoczki. Do zapamiętania kolejnych wyborów, algorytm Grahama używa stosu. Po zakończeniu działania algorytmu, na stosie znajdują się wszystkie wierzchołki szukanej otoczki wypukłej CH(Q) w kolejności ich występowania na obwodzie wielokąta.

Szkic Algorytmu

Wprawdzie w drugim kroku algorytmu jest mowa o porównywaniu kątów, ale nie jest konieczne ich obliczanie. Wystarczy nam informacja, który z nich jest mniejszy. To jednak możemy wyliczyć badając iloczyn wektorowy, tak jak w punkcie 2 tego wykładu.

Przykład 4.1

Rozważmy zbiór punktów przedstawiony na rysunku  13.7. Zgodnie z opisaną metodą wybierzemy, jako punkt p[0], punkt A. Na rysunku 13.7(a) zaznaczono kąty, ze względu na które  zbiór został uporządkowany. Aby stwierdzić np. że kąt jaki tworzy odcinek EA z dodatnim kierunkiem osi X, jest większy niż kąt jaki tworzy odcinek BA z dodatnią półosią X, wystarczy  stwierdzić, że punkt E leży na lewo od odcinka BA.  W trzecim kroku algorytmu na stos trafiają punkty A, B, C. Te trzy punkty tworzą wielokąt wypukły. Teraz przeglądamy wszystkie pozostałe punkty, aby stwierdzić, czy leżą one na lewo od ostatnio znalezionej krawędzi. W naszym przykładzie, punkt D leży na prawo od odcinka BC. Musimy więc zrezygnować z ostatnio wpisanego na stos punktu C. Ponieważ  D leży na lewo od odcinka AB więc dopiszemy D do stosu tworząc krawędź wielokąta. Następnym rozważanym punktem jest E. Znów stwierdzimy, że E znajduje się na prawo od BD, a więc musimy usunąć ze stosu punkt D. Punkt B znów pozostaje, bo E znajduje się na lewo od odcinka AB.  Stos zawiera teraz punkty A, B, E, a rozważanym punktem jest w tej chwili punkt F. itd... Gdy dojdziemy do punktu J stos będzie zawierał punkty ABEGHI. Ponieważ J znajduje się na prawo od HI oraz na prawo od GH , ale na lewo od krawędzi EG, więc musimy wycofać ze stosu kolejno I oraz H, a na ich miejsce wpisać wierzchołek J.

Poprawność algorytmu Grahama

Niech CH(Q) będzie zbiorem poszukiwanych wierzchołków otoczki wypukłej zbioru Q.

1. Punkty, które zostały usunięte ze stosu nie należą do otoczki wypukłej CH(Q).
Przypuśćmy, że w i-tej iteracji pętli "while"  punkt p[j] jest usuwany ze stosu, bo aktualnie rozważany  punkt p[i] leży na prawo od prostej wyznaczonej przez dwa ostatnio włożone na stos punkty p[k] i p[j] (por. rysunek 13.8).  Punkty p[i], p[0], p[k] nie są współliniowe, bo kąty jakie tworzą wektory p[0]p[i] oraz p[0]p[k] z dodatnim kierunkiem osi OX są różne (krok 2 ). Wynika stąd, że można utworzyć trójkąt  D(p[i],p[0],p[k]), w którego wnętrzu znajduje się punkt p[j]. Zatem p[j] nie może być wierzchołkiem budowanej otoczki wypukłej CH(Q) i dlatego możemy go usunąć ze stosu.

2. Punkt, który został dołączony do stosu tworzy razem z innymi na stosie, wielokąt wypukły.
Zauważmy najpierw, że dołączając do wielokąta wypukłego dowolny punktu z zakreskowanych na rysunku 13.9 obszarów, otrzymujemy nadal wielokąt wypukły. Niech ostatnio włożonymi na stos punktami będą p[k] i p[j]. Zgodnie z wykonanym testem, punkt p[i] zostanie dołączony do stosu, gdy leży po lewej stronie wektora  p[k]p[j]. Ponieważ ponadto kąt jaki tworzy wektor p[0]p[i] z dodatnim kierunkiem osi OX jest większy niż kąt jaki tworzy wektor p[0]p[j],  mamy gwarancję, że dołączany punkt należy do obszaru bezpiecznego.  Punkty znajdujące się na stosie tworzyć będą wielokąt wypukły.

Niezmiennik: zbiór punktów znajdujący się na stosie tworzy wielokąt wypukły, a wszystkie, do tej pory przejrzane, punkty zbioru Q znajdują się albo wewnątrz, albo na jego brzegach.

Ponieważ przed wykonaniem pętli for  niezmiennik jest spełniony i jest spełniony, gdy dołączamy nowy wierzchołek oraz po wykonaniu pętli "while", zatem po zakończeniu pętli "for" też jest spełniony. Zbiór punktów na stosie tworzy otoczkę wypukłą danego zbioru punktów Q.

Pytanie 5: Jeżeli wszystkie punkty zbioru Q znajdują się na obwodzie koła, to ile razy w algorytmie Grahama konstrukcji otoczki wypukłej dla zbioru Q wykonamy operację pop usuwania elementu włożonego na stos?