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 $O(kn),$ gdzie $n$ to całkowita liczba punktów, natomiast $k$ to liczba punktów należących do otoczki. Zwykle w praktyce $k\ll n,$ jednak w pesymistycznym przypadku złożoność czasowa może wynieść $O(n^{2}).$

Wariant 1

Przebieg algorytmu Jarvisa dla przykładowych danych

Algorytm przebiega następująco:

$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),
$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. $i:=1,$
2. powtarzaj:
  - $S:=P_{i},$
  - $P_{i+1}$ – punkt $N,$ dla którego kąt między wektorem $SN$ a wektorem $[1,0]$ jest najmniejszy; $N$ należy do otoczki,
  - jeśli $N=Q_{1},$ koniec iterowania,
  - $i:=i+1,$
wyznaczanie lewego łańcucha otoczki (czerwony):
1. $i:=1,$
2. powtarzaj:
  - $S:=Q_{i},$
  - $Q_{i+1}$ – punkt $N,$ dla którego kąt między wektorem $SN$ a wektorem $[-1,0]$ jest najmniejszy; $N$ należy do otoczki,
  - jeśli $N=P_{1},$ koniec iterowania,
  - $i:=i+1,$
ostatecznie otoczkę wypukłą określają punkty $P$ i $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ę.

$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),
$P_{0}:=[-\infty ,y(P_{1})],$
$i:=1,$
powtarzaj:
- $P_{i+1}$ – punkt $N,$ dla którego kąt $P_{i-1}P_{i}N$ jest największy,
- jeśli $N=P_{1},$ koniec iterowania,
- $i:=i+1,$
ostatecznie otoczkę tworzą punkty $P_{1\dots i}.$

Implementację można usprawnić, odrzucając w każdej iteracji punkty znajdujące się po prawej stronie wektora $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.

Zrzutuj punkty na płaszczyznę (np. XY) i wykonaj dwa pierwsze kroki algorytmu dla płaszczyzny:
- znajdź dolny punkt otoczki $P_{1},$
- oraz kolejny punkt na otoczce $P_{2}.$
Dodaj krawędź $P_{1}P_{2}$ do kolejki.
Dopóki kolejka nie pusta, powtarzaj:
- weź krawędź $AB$ z kolejki,
- znajdź taki punkt $C,$ aby wszystkie pozostałe punkty znalazły się po lewej stronie trójkąta $ABC,$
- trójkąt $ABC$ należy do otoczki,
- dodaj do kolejki dwie krawędzie nowego trójkąta: $AC$ i $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ż

Przypisy

↑ Donald R. Chand, Sham Kupur. An algorithm for convex polytypes. „JACM”, s. 78–86, 1970. (ang.).
↑ 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.

[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.).

[1]

[2]