Algorytm Grahama

Algorytm Grahama
Rodzaj	znajdowanie otoczki wypukłej
	Złożoność
Czasowa

Algorytm Grahama – efektywny algorytm wyszukiwania otoczki wypukłej skończonego zbioru punktów płaszczyzny; nie istnieją warianty dla przestrzeni o wyższych wymiarach. Pomysłodawcą algorytmu jest Ronald Graham^[1].

Czasowa złożoność obliczeniowa wynosi $O(n\log n).$

Algorytm przebiega następująco:

Wybierz punkt (ozn. O) o najniższej wartości współrzędnej y.
Przesuń wszystkie punkty tak, by punkt O pokrył się z początkiem układu współrzędnych.
Posortuj punkty leksykograficznie względem:
- kąta pomiędzy wektorem $OP_{i}$ a dodatnią osią układu współrzędnych,
- odległości punktu $P_{i}$ od początku układu współrzędnych.
Wybierz punkt (ozn. S) o najmniejszej współrzędnej y; jeśli kilka punktów ma tę samą współrzędną y, wybierz spośród nich ten o najmniejszej współrzędnej x.
Przeglądaj listę posortowanych punktów poczynając od punktu S:
- Od bieżącej pozycji weź trzy kolejne punkty (ozn. A, B, C).
- Jeśli punkt B leży na zewnątrz trójkąta AOC, to może należeć do otoczki wypukłej. Przejdź do następnego punktu na liście.
- Jeśli punkt B leży wewnątrz trójkąta AOC, to znaczy, że nie należy do otoczki. Usuń punkt B z listy i cofnij się o jedną pozycję (o ile bieżąca pozycja jest różna od początkowej).

Ze względu na wcześniejsze kroki algorytmu (sortowanie i sposób wybierania analizowanych trójek punktów) dwa z trzech warunków należenia punktu B do trójkąta AOC są spełnione, tj. B leży po „wewnętrznej” względem trójkąta stronie prostych OA i OC. Zatem do stwierdzenia przynależności do trójkąta wystarczy zbadać, po której stronie odcinka AC znajduje się punkt B, w tym celu wykorzystuje się znak iloczynu wektorowego $|C-A|\times |B-A|.$

W praktyce można również utożsamić krok 4. z 1., tzn. przyjąć, że $O=S.$

Przykładowy przebieg algorytmu

Zobacz też edytuj

Przypisy edytuj

↑ Ronald Graham. An efficient algorithm for determining the convex hull of a finite planar set. „Information Processing Letters”. 1, s. 132–133, 1972. (ang.).

Bibliografia edytuj

Mark de Berg, Mirosław Kowaluk: Geometria obliczeniowa. Algorytmy i zastosowania. Warszawa: Wydawnictwa Naukowo-Techniczne, 2007. ISBN 978-83-204-3244-2.
Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003, s. 263–267. ISBN 83-204-2796-7.

[1] Ronald Graham. An efficient algorithm for determining the convex hull of a finite planar set. „Information Processing Letters”. 1, s. 132–133, 1972. (ang.).

[1]