Kirkpatricks algoritm

Konstruktion av ett konvext skrov med "dela och erövra"-metoden - en algoritm för att konstruera ett konvext skrov .

Beskrivning

Givet en uppsättning poäng . $S$ $N$

Om ( är något litet heltal), konstruera ett konvext skrov med någon av de kända metoderna och sluta, annars gå till steg 2. ${\displaystyle N\leq N_{0))$ $N_{0}$
Låt oss dela upp den ursprungliga uppsättningen godtyckligt i två delmängder av ungefär lika stora och (låt den innehålla punkter och innehålla punkter). $S$ $S_{1}$ $S_{2}$ $S_{1}$ $N/2$ $S_{2}$ $NN/2$
Hitta rekursivt de konvexa skroven för var och en av delmängderna och . $S_{1}$ $S_{2}$
Vi konstruerar det konvexa skrovet av originaluppsättningen som det konvexa skrovet av föreningen av två konvexa polygoner och . $CH(S_{1})$ $CH(S_{2})$

Eftersom: , komplexiteten hos denna algoritm är lösningen av den rekursiva relationen , där är konstruktionstiden för det konvexa skrovet av föreningen av två konvexa polygoner, som var och en har nära hörn. Det kommer att visas härnäst att . $CH(S)=CH(S1\cup S2)=CH(CH(S_{1})\cup CH(S_{2}))$ $T(N)\leq 2T(N/2)+f(N)$ $f(N)$ $N/2$ $T(N)=O(N\log N)$

Definitioner

Stödlinjen till en konvex polygon är en linje som passerar genom någon vertex av polygonen på ett sådant sätt att alla inre punkter i polygonen ligger på samma sida av linjen . $P$ $l$ $P$ $l$

Till en konvex polygon kan du bygga stödlinjer från en punkt som inte hör till den. Vi använder det faktum att linjen , där är någon vertex av polygonen , är en stödlinje till om och endast om kanterna och ligger i samma halvplan som avgränsas av denna linje. Det är lätt att se att det i värsta fall krävs en korsning av polygonens hörn för att konstruera stödlinjerna , det vill säga de söks efter i linjär tid. $P$ $A$ ${\displaystyle AP_{i))$ $Pi}$ $P$ $P$ $(P_{i-1},P_{i})$ $(P_{i},P_{i+1})$ $P$

Implementering

Låt oss redan ha konstruerade konvexa skrov och . $P_{1}$ ${\displaystyle P_{2))$

Låt oss hitta någon inre punkt i polygonen (till exempel tyngdpunkten för tre hörn ). En sådan punkt kommer att vara en inre punkt . $A$ $P_{1}$ $P_{1}$ $A$ $CH(P_{1}\cup P_{2})$
Två fall är möjliga:
1. Punkten är inte en inre punkt i polygonen . Vi ritar två referenslinjer för polygonen som går genom punkten . Dessa referenslinjer passerar genom hörnen och polygonen . Alla punkter inuti triangeln tillhör inte gränsen för det konvexa skrovet . Alla andra punkter är ordnade efter polär vinkel i förhållande till punkten , genom att slå samman de två ordnade listorna med hörn i tid , och sedan tillämpa Graham -traversalmetoden på den resulterande listan , som endast kräver linjär tid. $A$ ${\displaystyle P_{2))$ ${\displaystyle P_{2))$ $A$ $B$ $C$ ${\displaystyle P_{2))$ $ABC$ $CH(P_{1}\cup P_{2})$ $A$ $O(N_{1})+O(N_{2})=O(N)$
2. Punkten är polygonens inre punkt . Ordna hörn av båda polygonerna runt mitten genom att slå samman de två ordnade listorna med hörn och bortom . $A$ ${\displaystyle P_{2))$ $A$ $P_{1}$ ${\displaystyle P_{2))$ $O(N)$
Nu kan Grahams algoritm appliceras på den resulterande listan med hörn, förutom fasen för sortering av punkter efter polära koordinater, då kommer den att exekveras i linjär tid.

Det konvexa skrovet för föreningen av konvexa polygoner erhålls nu . $P_{1}\cup P_{2}$

Algoritmens komplexitet

Totalt slutförs alla tre faserna av algoritmen i tid . Således får vi relationen , vars lösning, som bekant , är , som bestämmer komplexiteten hos algoritmen. $O(N)$ $f(N)=O(N)$ $T(N)\leq 2T(N/2)+O(N)$ $T(N)=O(N\log N)$

Länkar

http://www.cs.umd.edu/~samir/754/kshand.ps _