I beregningsgeometri er Jarvis walk en algoritme for beregning av det konvekse skroget til et endelig sett med punkter. Ideen med algoritmen er å " pakke " settet med punkter i en " gavepakke " : vi hekter dette papiret på et av punktene, vi strekker det, så snur vi rundt punktskyen.
La være det første punktet der papiret er hengt opp.
Det første punktet som papiret støter på vil være , så ... til det blir funnet .
Mer formelt, for hvert nye toppunkt i den konvekse konvolutten som er funnet, er det et spørsmål om å finne den neste ved å beregne poenget med minimum polar vinkel i forhold til .
I praksis deler vi ruten i to: fra punktet med minimum abscissa, deretter fra punktet med maksimum abscissa.
Linje (1) utføres som følger:
pour tout p' de E Si p'' = p' ou p' est à gauche de [pp') alors p'' = p' p := pKroppen av løkken gjentas - til utføres så mange ganger som det er punkter i den konvekse konvolutten. Linje (1) er inne . Derav en kompleksitet i , hvor representerer antall hjørner i den konvekse konvolutten.
(fr) [1] , Kurs ved University of Montpellier 2