Fast Shell algoritmus

A gyors hajótest  algoritmus egy konvex hajótest felépítésére szolgáló algoritmus egy síkon. Hoare gyorsrendezési ötletét használja

Leírás

A ponthalmaz két részhalmazra oszlik, amelyek mindegyike tartalmazni fog egy-egy szaggatott vonalat, amelyek összekapcsolása a konvex hajótest sokszögét adja.

  1. Vegyük az S halmaz két szélső pontját - a bal oldali L-t és a jobb oldali P-t. Rajzoljunk rajtuk egy egyenest. Jelölje S1 az A és P pontokon átmenő egyenes felett vagy azon lévő pontok részhalmazát, S2-vel pedig az alatta vagy ugyanazon az egyenesen elhelyezkedő pontok részhalmazát.
  2. Tekintsük az S1 felső részhalmazt. Azt a Pi pontot választjuk, amelyik a legnagyobb távolságra van az LP egyenestől (az LPiP háromszög területe a legnagyobb). Ha több ilyen pont van, akkor a legnagyobb szögű PiLP-t választjuk. A Pi pont a halmaz konvex héjának csúcsa. Valóban, ha a Pi ponton át húzunk egy, az LP egyenessel párhuzamos egyenest, akkor az S halmaznak egyetlen pontja sem lesz ezen egyenes felett. a választott választáshoz Pi a bal szélső közülük. Hogy. A Pi pont nem ábrázolható az S halmaz két másik pontjának konvex kombinációjával. Szerkesszük meg az LPi és PiP egyeneseket. A mindkét egyenestől jobbra elhelyezkedő pontok kihagyhatók a további vizsgálatból, mivel ezek az LPiP háromszög belső pontjai, vagyis nem tartoznak a CH(S), a konvex hajótest határához.
  3. Tekintsük most az S11 pontok részhalmazát, amelyek a ЛPi egyenestől balra vagy azon találhatók, és az S12 pontok részhalmazát, amelyek a PiП egyenestől balra vagy azon találhatók. Mindegyik részhalmazhoz készítünk egy konvex hajótestet. Az S1 halmaz konvex burkot a CH(S11) és CH(S12) csúcsok rendezett listáinak összeragasztásával alakítjuk ki.
  4. Megoldjuk az S2 problémáját.

Az algoritmus összetettsége

Az algoritmus összetettsége a figyelembe vett O(N) halmaz két részhalmazának megalkotásának bonyolultságából és az egyes részhalmazok részproblémák megoldásának bonyolultságából áll: T(N) = T(a) + T(b) + O( N).

A legjobb esetben, ha a feladatot két egyformán erős részfeladatra osztjuk, az algoritmus bonyolultsága a rekurzív egyenlet megoldása:

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

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

Legrosszabb esetben:

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

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

Lemma Az (1) egyenlet megoldása a (2) függvény. Legyen N = 2k. Ekkor 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 Ha m = k (= logN), az algoritmus véget ér: T(N) = NT(1) + C logN N = O(N logN)

Lásd még

Linkek