Algorytm Jarvisa

Algorytm Jarvisa, marsz Jarvisa lub owijanie prezentów (ang. gift wrapping algorithm) – metoda wyznaczania otoczki wypukłej zbioru punktów umieszczonych na płaszczyźnie lub przestrzeni o większej liczbie wymiarów.

Algorytm został niezależnie opracowany przez Donalda Chanda oraz Shama Kapura (1970)^[1] oraz R. Jarvisa (1973, przypadek na płaszczyźnie)^[2].

Algorytm na płaszczyźnie

Algorytm działa w czasie ${\displaystyle O(kn),}$ gdzie ${\displaystyle n}$ to całkowita liczba punktów, natomiast ${\displaystyle k}$ to liczba punktów należących do otoczki. Zwykle w praktyce ${\displaystyle k\ll n,}$ jednak w pesymistycznym przypadku złożoność czasowa może wynieść ${\displaystyle O(n^{2}).}$

Wariant 1

Przebieg algorytmu Jarvisa dla przykładowych danych

Algorytm przebiega następująco:

• ${\displaystyle P_{1}}$ – punkt na otoczce wypukłej o najmniejszej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o najmniejszej współrzędnej x),
• ${\displaystyle Q_{1}}$ – punkt na otoczce wypukłej o największej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o największej współrzędnej x),
• wyznaczanie prawego łańcucha otoczki (niebieski):
  1. ${\displaystyle i:=1,}$
  2. powtarzaj:
     • ${\displaystyle S:=P_{i},}$
     • ${\displaystyle P_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt między wektorem ${\displaystyle SN}$ a wektorem ${\displaystyle [1,0]}$ jest najmniejszy; ${\displaystyle N}$ należy do otoczki,
     • jeśli ${\displaystyle N=Q_{1},}$ koniec iterowania,
     • ${\displaystyle i:=i+1,}$
• wyznaczanie lewego łańcucha otoczki (czerwony):
  1. ${\displaystyle i:=1,}$
  2. powtarzaj:
     • ${\displaystyle S:=Q_{i},}$
     • ${\displaystyle Q_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt między wektorem ${\displaystyle SN}$ a wektorem ${\displaystyle [-1,0]}$ jest najmniejszy; ${\displaystyle N}$ należy do otoczki,
     • jeśli ${\displaystyle N=P_{1},}$ koniec iterowania,
     • ${\displaystyle i:=i+1,}$
• ostatecznie otoczkę wypukłą określają punkty ${\displaystyle P}$ i ${\displaystyle Q}$ (z pominięciem tych powtarzających się na granicach łańcuchów)

Wariant 2

Przebieg algorytmu Jarvisa dla przykładowych danych

Zamiast rozpatrywać dwa osobne łańcuchy, można od razu utworzyć całą otoczkę.

• ${\displaystyle P_{1}}$ – punkt na otoczce wypukłej o najmniejszej współrzędnej y (jeśli jest więcej niż jeden, wybierany jest ten o najmniejszej współrzędnej x),
• ${\displaystyle P_{0}:=[-\infty ,y(P_{1})],}$
• ${\displaystyle i:=1,}$
• powtarzaj:
  • ${\displaystyle P_{i+1}}$ – punkt ${\displaystyle N,}$ dla którego kąt ${\displaystyle P_{i-1}P_{i}N}$ jest największy,
  • jeśli ${\displaystyle N=P_{1},}$ koniec iterowania,
  • ${\displaystyle i:=i+1,}$
• ostatecznie otoczkę tworzą punkty ${\displaystyle P_{1\dots i}.}$

Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora ${\displaystyle P_{1}P_{i},}$ ponieważ na pewno nie będą należały do otoczki. Zabieg ten nie wpływa jednak na asymptotyczną złożoność obliczeniową algorytmu.

Algorytm w przestrzeni

Algorytm w przestrzeni znajduje wielościan wypukły, którego ścianami są trójkąty.

1. Zrzutuj punkty na płaszczyznę (np. XY) i wykonaj dwa pierwsze kroki algorytmu dla płaszczyzny:
   • znajdź dolny punkt otoczki ${\displaystyle P_{1},}$
   • oraz kolejny punkt na otoczce ${\displaystyle P_{2}.}$
2. Dodaj krawędź ${\displaystyle P_{1}P_{2}}$ do kolejki.
3. Dopóki kolejka nie pusta, powtarzaj:
   • weź krawędź ${\displaystyle AB}$ z kolejki,
   • znajdź taki punkt ${\displaystyle C,}$ aby wszystkie pozostałe punkty znalazły się po lewej stronie trójkąta ${\displaystyle ABC,}$
   • trójkąt ${\displaystyle ABC}$ należy do otoczki,
   • dodaj do kolejki dwie krawędzie nowego trójkąta: ${\displaystyle AC}$ i ${\displaystyle BC}$ (o ile nie były wcześniej przetwarzane).

Algorytm w wyższych wymiarach

Algorytm dla danych trójwymiarowych można uogólnić na przestrzenie o większej liczbie wymiarów.

Zobacz też

• algorytm Grahama
• quickhull

Przypisy

1. Donald R. Chand, Sham Kupur. An algorithm for convex polytypes. „JACM”, s. 78–86, 1970. (ang.). 
2. R.A. Jarvis. On the identification of the convex hull of a finite set of points in the plane. „Information Processing Letters”, s. 18–21, 1973. DOI: 10.1016/0020-0190(73)90020-3. (ang.). 

Bibliografia

• Lech Banachowski, Krzysztof Diks, Wojciech Rytter: Algorytmy i struktury danych. Warszawa: Wydawnictwa Naukowo-Techniczne, 2003, s. 267–268. ISBN 83-204-2796-7.