Algoritmus Chans - Chans algorithm - Wikipedia

2D ukázka pro Chanův algoritmus. Všimněte si však, že algoritmus dělí body libovolně, nikoli souřadnicí x.

v výpočetní geometrie, Chanův algoritmus,^[1] pojmenoval podle Timothy M. Chan, je optimální algoritmus citlivý na výstup vypočítat konvexní obal sady ${ displaystyle P}$ z ${ displaystyle n}$ body, ve 2- nebo 3-dimenzionálním prostoru. Algoritmus trvá ${ displaystyle O (n log h)}$ čas, kde ${ displaystyle h}$ je počet vrcholů výstupu (konvexní trup). V rovinném případě algoritmus kombinuje ${ displaystyle O (n log n)}$ algoritmus (Grahamovo skenování například) pomocí Jarvis pochod (${ displaystyle O (nh)}$), abychom získali optimální ${ displaystyle O (n log h)}$ čas. Chanův algoritmus je pozoruhodný, protože je mnohem jednodušší než Algoritmus Kirkpatrick – Seidel, a přirozeně se rozšiřuje do trojrozměrného prostoru. Toto paradigma^[2] byl nezávisle vyvinut Frank Nielsen v jeho Ph.D. teze.^[3]

Algoritmus

Přehled

Jeden průchod algoritmu vyžaduje parametr ${ displaystyle m}$ což je mezi 0 a ${ displaystyle n}$ (počet bodů naší sady ${ displaystyle P}$). Ideálně, ${ displaystyle m = h}$ ale ${ displaystyle h}$, počet vrcholů ve výstupním konvexním trupu, není na začátku znám. Několik průchodů s rostoucími hodnotami ${ displaystyle m}$ jsou hotové, které pak končí, když ${ displaystyle m geq h}$(viz níže o výběru parametru ${ displaystyle m}$).

Algoritmus začíná libovolným rozdělením množiny bodů ${ displaystyle P}$ do ${ displaystyle K = lceil n / m rceil}$ podmnožiny ${ displaystyle (Q_ {k}) _ {k = 1,2, ... K}}$ maximálně ${ displaystyle m}$ každý bod; všimněte si toho ${ displaystyle K = O (n / m)}$.

Pro každou podmnožinu ${ displaystyle Q_ {k}}$, počítá konvexní trup, ${ displaystyle C_ {k}}$pomocí ${ displaystyle O (p log p)}$ algoritmus (například Grahamovo skenování ), kde ${ displaystyle p}$ je počet bodů v podmnožině. Jak jsou ${ displaystyle K}$ podmnožiny ${ displaystyle O (m)}$ každý bod, tato fáze trvá ${ displaystyle K cdot O (m log m) = O (n log m)}$ čas.

Během druhé fáze Jarvisův pochod je proveden s využitím předpočítaných (mini) konvexních trupů, ${ displaystyle (C_ {k}) _ {k = 1,2, ... K}}$. V každém kroku tohoto Jarvisova pochodového algoritmu máme bod ${ displaystyle p_ {i}}$ v konvexním trupu (na začátku, ${ displaystyle p_ {i}}$ může být bod v ${ displaystyle P}$ s nejnižší souřadnicí y, která je zaručeně v konvexním trupu ${ displaystyle P}$) a potřebujete najít bod ${ displaystyle p_ {i + 1} = f (p_ {i}, P)}$ tak, že všechny ostatní body ${ displaystyle P}$ jsou napravo od čáry ${ displaystyle p_ {i} p_ {i + 1}}$^{[je zapotřebí objasnění ]}, kde notace ${ displaystyle p_ {i + 1} = f (p_ {i}, P)}$ jednoduše znamená, že další bod, to je ${ displaystyle p_ {i + 1}}$, je určena jako funkce ${ displaystyle p_ {i}}$ a ${ displaystyle P}$. Konvexní trup soupravy ${ displaystyle Q_ {k}}$, ${ displaystyle C_ {k}}$, je známo a obsahuje maximálně ${ displaystyle m}$ body (uvedené ve směru hodinových ručiček nebo proti směru hodinových ručiček), což umožňuje výpočet ${ displaystyle f (p_ {i}, Q_ {k})}$ v ${ displaystyle O ( log m)}$ čas do binární vyhledávání^{[jak? ]}. Proto je výpočet ${ displaystyle f (p_ {i}, Q_ {k})}$ pro všechny ${ displaystyle K}$ podmnožiny lze provádět v ${ displaystyle O (K log m)}$ čas. Poté můžeme určit ${ displaystyle f (p_ {i}, P)}$ pomocí stejné techniky, jaká se běžně používá při Jarvisově pochodu, ale pouze s ohledem na body ${ displaystyle (f (p_ {i}, Q_ {k})) _ {1 leq k leq K}}$ (tj. body v mini konvexních trupech) namísto celé sady ${ displaystyle P}$. Pro tyto body je jedna iterace Jarvisova pochodu ${ displaystyle O (K)}$ což je zanedbatelné ve srovnání s výpočtem pro všechny podmnožiny. Jarvisův pochod je dokončen, když se proces opakuje ${ displaystyle O (h)}$ krát (protože, způsobem, jakým Jarvis pochod funguje, po nanejvýš ${ displaystyle h}$ iterace jeho nejvzdálenější smyčky, kde ${ displaystyle h}$ je počet bodů v konvexním trupu ${ displaystyle P}$, museli jsme najít konvexní trup), proto trvá druhá fáze ${ displaystyle O (Kh log m)}$ čas, ekvivalent k ${ displaystyle O (n log h)}$ čas, pokud ${ displaystyle m}$ je blízko ${ displaystyle h}$ (viz níže popis zvolené strategie ${ displaystyle m}$ tak, že tomu tak je).

Spuštěním dvou výše popsaných fází, konvexní trup ${ displaystyle n}$ body jsou počítány v ${ displaystyle O (n log h)}$ čas.

Volba parametru ${ displaystyle m}$

Pokud je zvolena libovolná hodnota pro ${ displaystyle m}$, může se stát, že ${ displaystyle m$. V takovém případě po ${ displaystyle m}$ kroky ve druhé fázi přerušíme Jarvisův pochod protože jeho spuštění do konce by trvalo příliš dlouho. V tu chvíli, a ${ displaystyle O (n log m)}$ čas bude stráven a konvexní trup nebude vypočítán.

Cílem je provést několik průchodů algoritmu se zvyšujícími se hodnotami ${ displaystyle m}$; každý průchod končí (úspěšně nebo neúspěšně) v ${ displaystyle O (n log m)}$ čas. Li ${ displaystyle m}$ mezi průchody se zvyšuje příliš pomalu, počet iterací může být velký; na druhou stranu, pokud stoupá příliš rychle, první ${ displaystyle m}$ pro které je algoritmus úspěšně ukončen, může být mnohem větší než ${ displaystyle h}$a vytvářejí složitost ${ displaystyle O (n log m)> O (n log h)}$.

Srovnávací strategie

Jednou z možných strategií je náměstí hodnota ${ displaystyle m}$ při každé iteraci až do maximální hodnoty ${ displaystyle n}$ (odpovídá oddílu v sadách singletonů).^[4] Počínaje hodnotou 2 při iteraci ${ displaystyle t}$, ${ displaystyle m = min vlevo (n, 2 ^ {2 ^ {t}} vpravo)}$ je vybrán. V tom případě, ${ displaystyle O ( log log h)}$ iterace jsou prováděny, vzhledem k tomu, že algoritmus končí, jakmile máme

${ displaystyle m = 2 ^ {2 ^ {t}} geq h iff log left (2 ^ {2 ^ {t}} right) geq log h iff 2 ^ {t} geq log h iff log {2 ^ {t}} geq log { log h} iff t geq log { log h},}$

s logaritmem přijatým v základně ${ displaystyle 2}$a celková doba chodu algoritmu je

${ displaystyle sum _ {t = 0} ^ { lceil log log h rceil} O left (n log left (2 ^ {2 ^ {t}} right) right) = O (n) sum _ {t = 0} ^ { lceil log log h rceil} O (2 ^ {t}) = O left (n cdot 2 ^ {1+ lceil log log h rceil} right) = O (n log h).}$

Ve třech rozměrech

Zobecnit tuto konstrukci pro trojrozměrný případ, an ${ displaystyle O (n log n)}$ Místo Grahamova skenování by měl být použit algoritmus pro výpočet trojrozměrného konvexního trupu Preparaty a Honga a je třeba použít trojrozměrnou verzi pochodu Jarvise. Časová složitost zůstává ${ displaystyle O (n log h)}$.^[1]

Pseudo kód

V následujícím pseudokódu je text mezi závorkami a kurzívou komentáře. K úplnému pochopení následujícího pseudokódu se doporučuje, aby čtenář již byl obeznámen Grahamovo skenování a Jarvis pochod algoritmy pro výpočet konvexního trupu, ${ displaystyle C}$, ze sady bodů,${ displaystyle P}$.

Vstup: Soubor ${ displaystyle P}$ s ${ displaystyle n}$ bodů.

Výstup: Soubor ${ displaystyle C}$ s ${ displaystyle h}$ body, konvexní trup ${ displaystyle P}$.

(Vyberte bod ${ displaystyle P}$ který je zaručen v ${ displaystyle C}$: například bod s nejnižší souřadnicí y.)

(Tato operace trvá ${ displaystyle { mathcal {O}} (n)}$ čas: například můžeme jednoduše iterovat ${ displaystyle P}$.)

${ displaystyle p_ {1}: = PICK _START (P)}$

(${ displaystyle p_ {0}}$ se používá v Jarvisově pochodové části tohoto Chanova algoritmu,

abychom vypočítali druhý bod, ${ displaystyle p_ {2}}$, v konvexním trupu ${ displaystyle P}$.)

(Poznámka: ${ displaystyle p_ {0}}$ je ne bod ${ displaystyle P}$.)

(Další informace najdete v komentářích poblíž odpovídající části Chanova algoritmu.)

${ displaystyle p_ {0}: = (- infty, 0)}$

(Poznámka: ${ displaystyle h}$, počet bodů v konečném konvexním trupu ${ displaystyle P}$, je ne známý.)

(Toto jsou iterace potřebné k objevení hodnoty ${ displaystyle m}$, což je odhad ${ displaystyle h}$.)

(${ displaystyle h leq m}$ je vyžadováno, aby tento Chanův algoritmus našel konvexní trup ${ displaystyle P}$.)

(Přesněji řečeno, chceme ${ displaystyle h leq m leq h ^ {2}}$, aby se neprovádělo příliš mnoho zbytečných iterací

a tak je časová složitost tohoto Chanova algoritmu ${ displaystyle { mathcal {O}} (n log h)}$.)

(Jak je vysvětleno výše v tomto článku, používáme strategii, kde nanejvýš ${ displaystyle log log n}$ iterace jsou nutné najít ${ displaystyle m}$.)

(Poznámka: finále ${ displaystyle m}$ nemusí být rovno ${ displaystyle h}$, ale nikdy není menší než ${ displaystyle h}$ a větší než ${ displaystyle h ^ {2}}$.)

(Algoritmus tohoto Chan se nicméně jednou zastaví ${ displaystyle h}$ iterace nejvzdálenější smyčky jsou prováděny,

to je, i když ${ displaystyle m neq h}$, nefunguje ${ displaystyle m}$ iterace nejvzdálenější smyčky.)

(Další informace najdete v části tohoto algoritmu, která se týká pochodu Jarvis, níže.) ${ displaystyle C}$ se vrátí, pokud ${ displaystyle p_ {i + 1} == p_ {1}}$.)

pro ${ displaystyle 1 leq t leq log log n}$ dělat

(Nastavit parametr ${ displaystyle m}$ pro aktuální iteraci. Používáme „schéma kvadratury“, jak je popsáno výše v tomto článku.

Existují i ​​jiná schémata: například „schéma zdvojnásobení“, kde ${ displaystyle m = 2 ^ {t}}$, pro ${ displaystyle t = 1, tečky, left lceil log h right rceil}$.

Použijeme-li však „zdvojnásobovací schéma“, výsledná časová složitost tohoto Chanova algoritmu je ${ displaystyle { mathcal {O}} (n log ^ {2} h)}$.)

${ displaystyle m: = 2 ^ {2 ^ {t}}}$

(Inicializujte prázdný seznam (nebo pole) pro uložení bodů konvexního trupu ${ displaystyle P}$, jak se nacházejí.)

${ displaystyle C: = ()}$

${ displaystyle PŘIDAT (C, p_ {1})}$

(Libovolně rozdělená sada bodů ${ displaystyle P}$ do ${ displaystyle K = left lceil { frac {n} {m}} right rceil}$ podmnožiny zhruba ${ displaystyle m}$ každý prvek.)

${ displaystyle Q_ {1}, Q_ {2}, tečky, Q_ {K}: = SPLIT (P, m)}$

(Vypočítejte konvexní trup všech ${ displaystyle K}$ podmnožiny bodů, ${ displaystyle Q_ {1}, Q_ {2}, tečky, Q_ {K}}$.)

(Trvá to ${ displaystyle { mathcal {O}} (Km log m) = { mathcal {O}} (n log m)}$ čas.)

Li ${ displaystyle m leq h ^ {2}}$, pak je časová složitost ${ displaystyle { mathcal {O}} (n log h ^ {2}) = { mathcal {O}} (n log h)}$.)

pro ${ displaystyle 1 leq k leq K}$ dělat

(Vypočítejte konvexní trup podmnožiny ${ displaystyle k}$, ${ displaystyle Q_ {k}}$pomocí Grahamova skenování, které trvá ${ displaystyle { mathcal {O}} (m log m)}$ čas.)

(${ displaystyle C_ {k}}$ je konvexní trup podmnožiny bodů ${ displaystyle Q_ {k}}$.)

${ displaystyle C_ {k}: = GRAHAM _SCAN (Q_ {k})}$

(V tomto okamžiku jsou konvexní trupy ${ displaystyle C_ {1}, C_ {2}, tečky, C_ {K}}$ podmnožin bodů ${ displaystyle Q_ {1}, Q_ {2}, tečky, Q_ {K}}$ byly vypočítány.)

(Nyní použijte a upravená verze z Jarvis pochod algoritmus pro výpočet konvexního trupu ${ displaystyle P}$.)

(Jarvis pochod vystupuje v ${ displaystyle { mathcal {O}} (nh)}$ čas, kde ${ displaystyle n}$ je počet vstupních bodů a ${ displaystyle h}$ je počet bodů v konvexním trupu.)

(Vzhledem k tomu, že Jarvisův pochod je algoritmus citlivý na výstup, jeho doba provozu závisí na velikosti konvexního trupu, ${ displaystyle h}$.)

(V praxi to znamená, že Jarvis pochod vystupuje ${ displaystyle h}$ iterace jeho nejvzdálenější smyčky.

Při každé z těchto iterací se provádí maximálně ${ displaystyle n}$ iterace jeho nejvnitřnější smyčky.)

(Chceme ${ displaystyle h leq m leq h ^ {2}}$, takže nechceme hrát více než ${ displaystyle m}$ iterace v následující vnější smyčce.)

(Pokud je naše aktuální ${ displaystyle m}$ je menší než ${ displaystyle h}$, tj. ${ displaystyle m$, konvexní trup ${ displaystyle P}$ nemůže být nalezeno.)

(V této upravené verzi Jarvisova pochodu provádíme operaci uvnitř nejvnitřnější smyčky, která trvá ${ displaystyle { mathcal {O}} ( log m)}$ čas.

Proto je celková časová složitost této upravené verze

${ displaystyle { mathcal {O}} (mK log m) = { mathcal {O}} (m left lceil { frac {n} {m}} right rceil log m) = { mathcal {O}} (n log m) = { mathcal {O}} (n log 2 ^ {2 ^ {t}}) = { mathcal {O}} (n2 ^ {t}). }$

Li ${ displaystyle m leq h ^ {2}}$, pak je časová složitost ${ displaystyle { mathcal {O}} (n log h ^ {2}) = { mathcal {O}} (n log h)}$.)

pro ${ displaystyle 1 leq i leq m}$ dělat

(Poznámka: zde je bod v konvexním trupu ${ displaystyle P}$ je již známo, to je ${ displaystyle p_ {1}}$.)

(V tomto vnitřním pro smyčka, ${ displaystyle K}$ možné další body na konvexním trupu ${ displaystyle P}$, ${ displaystyle q_ {i, 1}, q_ {i, 2}, tečky, q_ {i, K}}$, jsou počítány.)

(Každý z těchto ${ displaystyle K}$ možné další body jsou z jiného ${ displaystyle C_ {k}}$:

to je ${ displaystyle q_ {i, k}}$ je možný další bod na konvexním trupu ${ displaystyle P}$ který je součástí konvexního trupu ${ displaystyle C_ {k}}$.)

(Poznámka: ${ displaystyle q_ {i, 1}, q_ {i, 2}, tečky, q_ {i, K}}$ záleží na ${ displaystyle i}$: to znamená pro každou iteraci ${ displaystyle i}$, my máme ${ displaystyle K}$ možné další body na konvexním trupu ${ displaystyle P}$.)

(Poznámka: při každé iteraci ${ displaystyle i}$, pouze jeden z bodů mezi ${ displaystyle q_ {i, 1}, q_ {i, 2}, tečky, q_ {i, K}}$ je přidán do konvexního trupu ${ displaystyle P}$.)

pro ${ displaystyle 1 leq k leq K}$ dělat

(${ displaystyle JARVIS _BINARY _SEARCH}$ najde bod ${ displaystyle d v C_ {k}}$ takový, že úhel ${ displaystyle změřený úhel p_ {i-1} p_ {i} d}$ je maximalizován^{[proč? ]},

kde ${ displaystyle změřený úhel p_ {i-1} p_ {i} d}$ je úhel mezi vektory ${ displaystyle { overrightarrow {p_ {i} p_ {i-1}}}}$ a ${ displaystyle { overrightarrow {p_ {i} d}}}$. Takový ${ displaystyle d}$ je uložen v ${ displaystyle q_ {i, k}}$.)

(Úhly není nutné počítat přímo: orientační test může být použito^{[jak? ]}.)

(${ displaystyle JARVIS _BINARY _SEARCH}$ lze provést v ${ displaystyle { mathcal {O}} ( log m)}$ čas^{[jak? ]}.)

(Poznámka: při iteraci ${ displaystyle i = 1}$, ${ displaystyle p_ {i-1} = p_ {0} = (- infty, 0)}$ a ${ displaystyle p_ {1}}$ je znám a je bodem v konvexním trupu ${ displaystyle P}$:

v tomto případě jde o ${ displaystyle P}$ s nejnižší souřadnicí y.)

${ displaystyle q_ {i, k}: = JARVIS _BINARY _SEARCH (p_ {i-1}, p_ {i}, C_ {k})}$

(Vyberte bod ${ displaystyle z in {q_ {i, 1}, q_ {i, 2}, tečky, q_ {i, K} }}$ což maximalizuje úhel ${ displaystyle změřený úhel p_ {i-1} p_ {i} z}$^{[proč? ]} být dalším bodem na konvexním trupu ${ displaystyle P}$.)

${ displaystyle p_ {i + 1}: = JARVIS _NEXT _CH _POINT (p_ {i-1}, p_ {i}, (q_ {i, 1}, q_ {i, 2}, dots, q_ {i, K}))}$

(Jarvisův pochod končí, když je další vybraný bod na konvexním trupu, ${ displaystyle p_ {i + 1}}$, je počáteční bod, ${ displaystyle p_ {1}}$.)

-li ${ displaystyle p_ {i + 1} == p_ {1}}$

(Vraťte konvexní trup ${ displaystyle P}$ který obsahuje ${ displaystyle i = h}$ bodů.)

(Poznámka: samozřejmě není třeba se vracet ${ displaystyle p_ {i + 1}}$ což se rovná ${ displaystyle p_ {1}}$.)

vrátit se ${ displaystyle C: = (p_ {1}, p_ {2}, tečky, p_ {i})}$

jiný

${ displaystyle PŘIDAT (C, p_ {i + 1})}$

(Pokud po ${ displaystyle m}$ iterace bod ${ displaystyle p_ {i + 1}}$ nebyl nalezen, takže ${ displaystyle p_ {i + 1} == p_ {1}}$, pak ${ displaystyle m$.)

(Musíme začít znovu s vyšší hodnotou pro ${ displaystyle m}$.)

Implementace

Chanův dokument obsahuje několik návrhů, které mohou zlepšit praktickou výkonnost algoritmu, například:

• Při výpočtu konvexních trupů podmnožin vylučujte body, které nejsou v konvexním trupu, z úvah v následujících popravách.
• Konvexní trupy větších bodových sad lze získat sloučením dříve vypočtených konvexních trupů namísto přepočítávání od nuly.
• S výše uvedenou myšlenkou spočívá dominantní cena algoritmu v předběžném zpracování, tj. Ve výpočtu konvexních trupů skupin. Abychom tuto cenu snížili, můžeme zvážit opětovné použití trupů vypočítaných z předchozí iterace a jejich sloučení, jak se zvětší velikost skupiny.

Rozšíření

Chanův článek obsahuje některé další problémy, jejichž známé algoritmy lze pomocí jeho techniky nastavit na optimální výstup citlivý, například:

• Výpočet spodní obálky ${ displaystyle L (S)}$ sady ${ displaystyle S}$ z ${ displaystyle n}$ úsečky, která je definována jako spodní hranice neomezeného lichoběžník tvořené křižovatkami.
• Hershberger^[5] dal ${ displaystyle O (n log n)}$ algoritmus, který lze zrychlit ${ displaystyle O (n log h)}$, kde h je počet hran v obálce

• Konstrukce algoritmů citlivých na výstup pro konvexní trupy s vyšší dimenzí. S využitím seskupovacích bodů a pomocí efektivních datových struktur ${ displaystyle O (n log h)}$ složitosti lze dosáhnout za předpokladu, že h je polynomiálního řádu v ${ displaystyle n}$.

Viz také

• Konvexní trupové algoritmy

Reference