Kirkpatrick algoritmusa

Konvex hajótest építése az "oszd meg és uralkodj" módszerrel - egy konvex hajótest felépítésének algoritmusa .

Leírás

Adott egy pontkészlet . $S$ $N$

Ha ( valami kis egész szám), akkor az ismert módszerek egyikével készítsen konvex hajótestet, és álljon meg, ellenkező esetben folytassa a 2. lépéssel. ${\displaystyle N\leq N_{0))$ $N_{0}$
Osszuk fel az eredeti halmazt tetszőlegesen két, megközelítőleg egyforma méretű részhalmazra és (legyen benne pont, és tartalmazzon pontokat). $S$ $S_{1}$ $S_{2}$ $S_{1}$ $N/2$ $S_{2}$ $NN/2$
Keresse meg rekurzívan az egyes részhalmazok konvex héját és . $S_{1}$ $S_{2}$
Az eredeti halmaz konvex héját két konvex sokszög és . $CH(S_{1})$ $CH(S_{2})$

Mivel: , ennek az algoritmusnak a bonyolultsága a rekurzív reláció megoldása , ahol két konvex sokszög unió konvex burkának építési ideje, amelyek mindegyikének van közeli csúcsa. Legközelebb ez lesz látható . $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)$

Definíciók

A konvex sokszög támaszvonala egy olyan egyenes , amely a sokszög valamely csúcsán megy át úgy, hogy a sokszög minden belső pontja az egyenes ugyanazon az oldalán fekszik . $P$ $l$ $P$ $l$

Egy konvex sokszöghez támasztóvonalakat építhet olyan pontból , amely nem tartozik hozzá. Azt a tényt használjuk, hogy a vonal , ahol a sokszög valamely csúcsa, akkor és csak akkor támasztóvonal, ha az élek és az élek ugyanabban a félsíkban vannak, amelyet ez az egyenes határol. Könnyen belátható, hogy legrosszabb esetben a sokszög csúcsainak egyszeri bejárása szükséges a támaszvonalak felépítéséhez , azaz lineáris időben keresik őket. $P$ $A$ ${\displaystyle AP_{i))$ $P_{i}$ $P$ $P$ $(P_{i-1},P_{i})$ ${\megjelenítési stílus (P_{i}, P_{i+1})}$ $P$

Megvalósítás

Legyen már megszerkesztett konvex hajótestünk és . $P_{1}$ ${\displaystyle P_{2))$

Keressük meg a sokszög valamely belső pontját (például bármelyik három csúcs súlypontját ). Egy ilyen pont belső pont lesz . $A$ $P_{1}$ $P_{1}$ $A$ $CH(P_{1}\cup P_{2})$
Két eset lehetséges:
1. A pont nem a sokszög belső pontja . A ponton átmenő sokszögre két referenciavonalat rajzolunk . Ezek a referenciavonalak áthaladnak a csúcsokon és a sokszögön . A háromszög belsejében lévő összes pont nem tartozik a konvex hajótest határához . Az összes többi pontot a ponthoz viszonyított poláris szög szerint rendezzük úgy, hogy a két rendezett csúcslistát időben összevonjuk , majd a Graham bejárási módszert alkalmazzuk a kapott listára , amely csak lineáris időt igényel. $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. A pont a sokszög belső pontja . Rendezze mindkét sokszög csúcsait a középpont körül úgy, hogy összevonja a két rendezett csúcslistát és azon túl . $A$ ${\displaystyle P_{2))$ $A$ $P_{1}$ ${\displaystyle P_{2))$ $O(N)$
Most Graham algoritmusa alkalmazható a kapott csúcslistára, kivéve a pontok poláris koordináta szerinti rendezési fázisát, akkor lineáris időben kerül végrehajtásra.

Most megkapjuk a konvex sokszögek uniójának konvex héját . $P_{1}\cup P_{2}$

Az algoritmus összetettsége

Összességében az algoritmus mindhárom fázisa időben befejeződik . Így megkapjuk a relációt , amelynek megoldása, mint ismeretes , , amely meghatározza az algoritmus bonyolultságát. $O(N)$ $f(N)=O(N)$ $T(N)\leq 2T(N/2)+O(N)$ $T(N)=O(N\log N)$

Linkek

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