Kirkpatrickův algoritmus

Konstrukce konvexního trupu metodou "rozděl a panuj" - algoritmus pro konstrukci konvexního trupu .

Popis

Daný soubor bodů . $S$ $N$

Pokud ( je nějaké malé celé číslo), pak vytvořte konvexní obal pomocí jedné ze známých metod a zastavte se, jinak přejděte ke kroku 2. ${\displaystyle N\leq N_{0))$ $N_{0}$
Původní množinu rozdělme libovolně na dvě podmnožiny přibližně stejné velikosti a (nechť obsahuje body a obsahuje body). $S$ $S_{1}$ $S_{2}$ $S_{1}$ $N/2$ $S_{2}$ $NN/2$
Rekurzivně najděte konvexní obaly každé z podmnožin a . $S_{1}$ $S_{2}$
Konvexní obal původní sady sestrojíme jako konvexní obal spojení dvou konvexních polygonů a . $CH(S_{1})$ $CH(S_{2})$

Protože: , složitost tohoto algoritmu je řešením rekurzivního vztahu , kde je doba výstavby konvexního obalu spojení dvou konvexních polygonů, z nichž každý má blízké vrcholy. Dále se ukáže, že . $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)$

Definice

Podpůrná čára konvexního mnohoúhelníku je čára procházející některým vrcholem mnohoúhelníku tak, že všechny vnitřní body mnohoúhelníku leží na stejné straně úsečky . $P$ $l$ $P$ $l$

Ke konvexnímu mnohoúhelníku můžete vytvořit podpůrné čáry z bodu , který do něj nepatří. Využijeme toho, že úsečka , kde je nějaký vrchol polygonu , je podpěrnou úsečkou právě tehdy, když hrany a leží ve stejné polorovině ohraničené touto úsečkou. Je snadné vidět, že v nejhorším případě je k sestrojení podpěrných čar zapotřebí jeden průchod vrcholy polygonu , to znamená, že se hledají v lineárním čase. $P$ $A$ ${\displaystyle AP_{i))$ $P_{i}$ $P$ $P$ $(P_{i-1},P_{i})$ $(P_{i},P_{i+1})$ $P$

Implementace

Už máme zkonstruované konvexní trupy a . $P_{1}$ ${\displaystyle P_{2))$

Najdeme nějaký vnitřní bod polygonu (například těžiště libovolných tří vrcholů ). Takový bod bude vnitřním bodem . $A$ $P_{1}$ $P_{1}$ $A$ $CH(P_{1}\cup P_{2})$
Jsou možné dva případy:
1. Bod není vnitřním bodem mnohoúhelníku . Nakreslíme dvě referenční čáry pro mnohoúhelník procházející bodem . Tyto referenční čáry procházejí vrcholy a polygonem . Všechny body uvnitř trojúhelníku nepatří k hranici konvexního trupu . Všechny ostatní body jsou seřazeny podle polárního úhlu vzhledem k bodu , sloučením dvou uspořádaných seznamů vrcholů v čase a následným použitím Grahamovy traversální metody na výsledný seznam , vyžadující pouze lineární čas. $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. Bod je vnitřní bod mnohoúhelníku . Uspořádejte vrcholy obou polygonů kolem středu sloučením dvou uspořádaných seznamů vrcholů a dále . $A$ ${\displaystyle P_{2))$ $A$ $P_{1}$ ${\displaystyle P_{2))$ $O(N)$
Nyní lze Grahamův algoritmus aplikovat na výsledný seznam vrcholů, kromě fáze řazení bodů podle polárních souřadnic, pak bude proveden v lineárním čase.

Nyní je získán konvexní obal spojení konvexních polygonů . $P_{1}\cup P_{2}$

Složitost algoritmu

Celkově jsou všechny tři fáze algoritmu dokončeny včas . Získáme tak vztah , jehož řešením, jak známo , je , který určuje složitost algoritmu. $O(N)$ $f(N)=O(N)$ $T(N)\leq 2T(N/2)+O(N)$ $T(N)=O(N\log N)$

Odkazy

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