Algoritam uvijanja poklona

Uvijanje poklona je algoritam računarske geometrije za pronalaženje konveksnog omotača datog skupa tačaka.

Uvod[uredi | uredi izvor]

U slučaju ravni algoritam uvijanja poklona se naziva još i Džarvisov marš, po R. A. Džarvisu koji ga je objavio 1973. godine. Algoritam uvijanja poklona je dobio naziv po načinu na koji se pronalaze tačke konveksnog omotača. Ako zamislimo da su na mestima tačaka zabodene uspravne čiode, algoritam se može objasniti pomoću konca (omotača) koji zavežemo za početnu čiodu zategnemo ga na napolje a zatim obmotamo oko skupa tačaka, odnosno čioda, obuhvativši time ceo skup unutar konca. Algoritam uvijanja poklona je nastao kao optimizacija direktnog geometrijskog pristupa za određivanje konveksnog omotača. U slučaju trodimenzionalnog skupa tačaka umesto konca bismo koristili koristili papir za uvijanje, odakle dolazi i naziv.

Algoritam[uredi | uredi izvor]

Ovaj algoritam se zasniva na postepenom proširivanju puta konveksnog omotača. Osnova algoritma je izabiranje ekstremne tačke datog skupa, koja zasigurno pripada konveksnom omotaču. Uzmimo za ekstremnu tačku onu sa najmanjom x-koordinatom, a ukoliko ima više takvih onu sa najmanjom y-koordinatom. Označimo početnu tačku sa p¹. Prolazeći kroz sve tačke skupa, pronalazimo onu koja zajedno sa početnom tačkom zaklapa najmanji ugao sa x-osom. Nova tačka dobija vrednost p². Postupak se zatim ponavlja za novu tačku omotača. Pronalaženje sledeće tačke omotača zahteva n-k koraka, gde je n ukupan broj tačaka, a k broj pronađenih tačaka omotača, što zahteva vremensku složenost od O(n).

Pseudokod[uredi | uredi izvor]

U narednom pseudokodu pretpostavićemo da je izabrana početna tačka ona sa najvećom h koordinatom, odnosno najdesnija tačka skupa. Ukoliko ima dve ili više tačaka sa najvećom h kooridnatom izabraćemo među njima onu sa najmanjom u koordinatom.

Uvijanje poklona
`Улаз: p₁, p₂ , ...,p_n (скуп тачака у равни).` `Излаз: P (конвексни омотач тачака p₁, p₂ , ...,p_n begin` Нека је P празан скуп; Нека је p тачка са највећом x-координатом; (и са најмањом y-коориднатом, ako има више тачака са највећом x-координатом); Укључи p у скуп P ; Нека је L права паралелна са x-осом; while омотач P није завршен do Нека је q тачка за коју је најмањи угао између L и –p–q–; Укључи q у скуп P ; L := права –p–q– ; p := q; `end`

Induktivna hipoteza[uredi | uredi izvor]

Matematička osnova za primenu algoritma za uvijanje poklona je geometrijski metod za određivanje konveksnog omotača skupa tačaka. Oba metoda se dokazuju indukcijom. AUP je direktna posledica primene sledeće induktivne hipoteze:

Za dati skup od n tačaka u ravni, umemo da pronađemo konveksni put dužine k < n koji je deo konveksnog omotača skupa.

Vremenska složenost[uredi | uredi izvor]

Za svaku tačku treba izračunati uglove između pravih ka svim preostalim temenima i x-ose i zatim pronaći minimalni ugao u skupu od n-k pravih. Vremenska složenost u opštem slučaju je O(nh) gde je h broj tačaka konveksnog omotača. U najgorem slučaju, sve tačke skupa mogu da pripadaju omotaču i pa je stoga vremenska složenost algoritma uvijanja poklona O(n²).

Literatura[uredi | uredi izvor]

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. „33.3: Finding the convex hull”. Introduction to Algorithms (2nd izd.). MIT Press and McGraw-Hill. str. 955—956. ISBN 0-262-03293-7.
Jarvis, R. A. (1973). „On the identification of the convex hull of a finite set of points in the plane”. Information Processing Letters. 2: 18—21. doi:10.1016/0020-0190(73)90020-3.

Spoljašnje veze[uredi | uredi izvor]