Algoritmus rychlého shellu

Algoritmus rychlého trupu  je algoritmus pro konstrukci konvexního trupu v rovině. Využívá Hoareovu myšlenku rychlého třídění

Popis

Sada bodů je rozdělena na dvě podmnožiny, z nichž každá bude obsahovat jednu z přerušovaných čar, jejichž spojením vznikne konvexní polygon trupu.

  1. Vezměme si dva krajní body množiny S - levý L a pravý P. Proveďme jimi přímku. Označme S1 podmnožinu bodů umístěných nad nebo na přímce procházející body A a P a S2 podmnožinu bodů umístěných pod nebo na téže přímce.
  2. Uvažujme horní podmnožinu S1. Zvolíme bod Pi, který má největší vzdálenost od přímky LP (největší plochu má trojúhelník LPiP). Pokud je takových bodů více, vybereme ten s největším úhlem PiLP. Bod Pi je vrcholem konvexního trupu množiny. Pokud totiž bodem Pi vede přímka rovnoběžná s přímkou ​​LP, pak nad touto přímkou ​​nebude jediný bod množiny S. Je možné, že na sestrojené přímce budou další body, ale podle k provedené volbě je Pi z nich úplně vlevo. Že. Bod Pi nemůže být reprezentován konvexní kombinací dvou dalších bodů množiny S. Sestrojme přímky LPi a PiP. Body umístěné napravo od obou přímek mohou být z další úvahy vyloučeny, protože jsou vnitřními body trojúhelníku LPiP, to znamená, že nepatří do CH(S), hranice konvexního trupu.
  3. Nyní zvažte podmnožinu bodů S11 umístěných vlevo od přímky ЛPi nebo na ní a podmnožinu bodů S12 umístěných vlevo od přímky PiП nebo na ní. Pro každou z podmnožin zkonstruujeme konvexní trup. Konvexní obal množiny S1 vznikne slepením uspořádaných seznamů vrcholů CH(S11) a CH(S12).
  4. Řešíme problém pro S2.

Složitost algoritmu

Složitost algoritmu spočívá ve složitosti konstrukce dvou podmnožin uvažované množiny O(N) a složitosti řešení podproblémů pro každou z podmnožin: T(N) = T(a) + T(b) + O( N).

V nejlepším případě, kdy je úloha rozdělena do dvou stejně výkonných dílčích úloh, je složitost algoritmu řešením rekurzivní rovnice:

(1) T(N) = 2 T(N/2) + O(N) =>

(2) T(N) = O(N log N).

Při nejhorším:

(3) T(N) = T(1) + T(N1) + O(N) =>

(4) T(N) = O(N^2).

Lemma Řešením rovnice (1) je funkce (2) Nechť N = 2k. Potom T(2k) = 2 T(2k 1) + C 2k ; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m C 2k Pro m = k (= logN) algoritmus končí: T(N) = NT(1) + C logN N = O(N logN)

Viz také

Odkazy