Uvažujte obecný případ, kdy je vstupem algoritmu konečná neuspořádaná množina bodů v kartézské rovině. Důležitý speciální případ, kdy jsou body zadány v pořadí, v jakém procházejí hranicí jednoduchého mnohoúhelníku, je popsán později v samostatné podkapitole.
Pokud nejsou všechny body na stejné přímce, pak je jejich konvexní trup konvexní mnohoúhelník, jehož vrcholy jsou některé z bodů vstupní množiny. Jeho nejběžnější reprezentací je seznam jeho vrcholů uspořádaných podél jeho hranice ve směru nebo proti směru hodinových ručiček. V některých aplikacích je výhodné reprezentovat konvexní mnohoúhelník jako průsečík množiny polopřímek.
Dolní hranice výpočetní složitostiEdit
Pro konečnou množinu bodů v rovině se snadno ukáže, že dolní hranice výpočetní složitosti nalezení konvexního trupu reprezentovaného jako konvexní mnohoúhelník je stejná jako pro třídění pomocí následující redukce. Pro množinu x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}.
čísla pro třídění uvažujte množinu bodů ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\dots ,(x_{n},x_{n}^{2})}
bodů v rovině. Protože leží na parabole, která je konvexní křivkou, je snadné vidět, že vrcholy konvexního trupu při průchodu podél hranice vytvářejí uspořádané pořadí čísel x 1 , … , x n {\displayystyle x_{1},\dots ,x_{n}}.
. Je zřejmé, že na popsanou transformaci čísel na body a následné získání jejich seřazeného pořadí je zapotřebí lineární čas. Proto v obecném případě nelze konvexní plášť n bodů vypočítat rychleji než třídění.
Standardní dolní mez Ω(n log n) pro třídění je dokázána v modelu výpočetního rozhodovacího stromu, v němž lze provádět pouze číselná porovnání, ale ne aritmetické operace; v tomto modelu však konvexní trupy nelze vypočítat vůbec. Třídění vyžaduje Ω(n log n) času také v algebraickém modelu výpočtu rozhodovacích stromů, což je model vhodnější pro konvexní trupy, a v tomto modelu konvexní trupy také vyžadují Ω(n log n) času. V modelech počítačové aritmetiky, které umožňují třídit čísla rychleji než v čase O(n log n), například pomocí celočíselných třídicích algoritmů, lze však planární konvexní trupy počítat také rychleji: Grahamův skenovací algoritmus pro konvexní trupy se skládá z jediného kroku třídění, po němž následuje lineární množství další práce.
Optimální výstupně citlivé algoritmyUpravit
Jak bylo uvedeno výše, složitost nalezení konvexního trupu jako funkce velikosti vstupu n je dolní hranicí Ω(n log n). Složitost některých algoritmů hledání konvexního trupu však lze charakterizovat jak velikostí vstupu n, tak velikostí výstupu h (počtem bodů v trupu). Takové algoritmy se nazývají výstupně citlivé algoritmy. Mohou být asymptoticky efektivnější než Θ(n log n) algoritmy v případech, kdy h = o(n).
Dolní mez pro nejhorší případ běhu výstupně citlivých algoritmů konvexního trupu byla stanovena na Ω(n log h) v planárním případě. Existuje několik algoritmů, které této optimální časové složitosti dosahují. Nejstarší z nich představili Kirkpatrick a Seidel v roce 1986 (nazvali jej „konečný algoritmus konvexního trupu“). Mnohem jednodušší algoritmus vyvinul Chan v roce 1996 a nazývá se Chanův algoritmus.
AlgoritmyEdit
Známé algoritmy konvexního trupu jsou uvedeny níže, seřazené podle data prvního zveřejnění. Časová složitost každého algoritmu je uvedena v počtu vstupních bodů n a počtu bodů na trupu h. Všimněte si, že v nejhorším případě může být h stejně velké jako n.
- Gift wrapping, alias Jarvisův pochod – O(nh)
Jeden z nejjednodušších (i když v nejhorším případě ne časově nejefektivnějších) planárních algoritmů. Vytvořili nezávisle na sobě Chand & Kapur v roce 1970 a R. A. Jarvis v roce 1973. Má časovou složitost O(nh), kde n je počet bodů v množině a h je počet bodů v trupu. V nejhorším případě je složitost Θ(n2). - Grahamovo skenování – O(n log n)
Mírně složitější, ale mnohem efektivnější algoritmus publikoval Ronald Graham v roce 1972. Pokud jsou body již seřazeny podle jedné ze souřadnic nebo podle úhlu k pevnému vektoru, pak algoritmus trvá O(n) času. - Quickhull
Vytvořil nezávisle na sobě v roce 1977 W. Eddy a v roce 1978 A. Bykat. Stejně jako algoritmus quicksort má očekávanou časovou složitost O(n log n), ale v nejhorším případě může degenerovat na O(n2). - Rozděl a panuj – O(n log n)
Další algoritmus O(n log n), publikovaný v roce 1977 Preparatem a Hongem. Tento algoritmus je použitelný i pro třírozměrný případ. - Monotónní řetězec alias Andrewův algoritmus – O(n log n)
Publikoval v roce 1979 A. M. Andrew. Algoritmus lze považovat za variantu Grahamova skenování, které řadí body lexikograficky podle jejich souřadnic. Pokud je vstup již setříděn, algoritmus trvá O(n) času. - Algoritmus inkrementálního konvexního trupu – O(n log n)
Publikoval v roce 1984 Michael Kallay. - Algoritmus Kirkpatrick-Seidel – O(n log h)
První optimální algoritmus citlivý na výstup. Modifikuje algoritmus rozděl a panuj pomocí techniky sňatku před dobytím a nízkorozměrného lineárního programování. Publikovali Kirkpatrick a Seidel v roce 1986. - Chanův algoritmus – O(n log h)
Jednodušší optimální algoritmus citlivý na výstup vytvořil Chan v roce 1996. Kombinuje dárkové balení s prováděním algoritmu O(n log n) (například Grahamovo skenování) na malých podmnožinách vstupu.
Akl-Toussaintova heuristikaEdit
Následující jednoduchá heuristika se často používá jako první krok v implementacích algoritmů konvexního trupu ke zlepšení jejich výkonu. Vychází z efektivního algoritmu konvexního trupu autorů Selima Akla a G. T. Toussainta z roku 1978. Jeho podstatou je rychlé vyloučení mnoha bodů, které by stejně nebyly součástí konvexního trupu. Tato metoda je založena na následující myšlence. Najděte dva body s nejnižší a nejvyšší x-ovou souřadnicí a dva body s nejnižší a nejvyšší y-ovou souřadnicí. (Každá z těchto operací trvá O(n).) Tyto čtyři body tvoří konvexní čtyřúhelník a všechny body, které leží v tomto čtyřúhelníku (kromě čtyř původně zvolených vrcholů), nejsou součástí konvexního trupu. Nalezení všech těchto bodů, které leží v tomto čtyřúhelníku, je také O(n), a celá operace je tedy O(n). Volitelně lze do čtyřúhelníku přidat také body s nejmenšími a největšími součty souřadnic x a y a body s nejmenšími a největšími rozdíly souřadnic x a y, čímž vznikne nepravidelný konvexní osmiúhelník, jehož vnitřky lze bezpečně zahodit. Pokud jsou body náhodnými veličinami, pak pro úzkou, ale běžně se vyskytující třídu funkcí hustoty pravděpodobnosti tento krok předběžného zpracování, který se vyhazuje, umožní, aby algoritmus konvexního trupu běžel v lineárním očekávaném čase, i když je složitost algoritmu konvexního trupu v nejhorším případě kvadratická v n.
On-line a dynamické problémy konvexního trupuRedakce
Výše uvedená diskuse uvažuje případ, kdy jsou všechny vstupní body známy předem. Lze uvažovat dvě další nastavení.
- On-line problém konvexního trupu: Vstupní body jsou získávány postupně jeden po druhém. Po příchodu každého bodu na vstup je třeba efektivně vypočítat konvexní trup pro dosud získanou množinu bodů.
- Dynamická údržba konvexního trupu:
Vložení bodu může zvýšit počet vrcholů konvexního trupu nejvýše o 1, zatímco odstranění může přeměnit n-vrcholový konvexní trup na n-1-vrcholový.
Online verzi lze zvládnout s O(log n) na bod, což je asymptoticky optimální. Dynamickou verzi lze zpracovat s O(log2 n) na operaci.
Jednoduchý polygonEdit
Konvexní trup jednoduchého mnohoúhelníku je rozdělen mnohoúhelníkem na části, z nichž jedna je samotný mnohoúhelník a ostatní jsou kapsy ohraničené kusem hranice mnohoúhelníku a jednou hranou trupu. Přestože pro problém konstrukce konvexního trupu jednoduchého mnohoúhelníku bylo publikováno mnoho algoritmů, téměř polovina z nich je nesprávná. první správný algoritmus poskytli McCallum a Avis. pozdější zjednodušení od Grahama & Yao (1983) a Leeho (1983) používá pouze jednu datovou strukturu zásobníku. Jejich algoritmus prochází mnohoúhelník ve směru hodinových ručiček, přičemž začíná od jeho nejlevějšího vrcholu. Přitom ukládá na zásobník konvexní posloupnost vrcholů, tedy těch, které ještě nebyly identifikovány jako ležící v kapsách. V každém kroku algoritmus sleduje cestu podél mnohoúhelníku od vrcholu zásobníku k dalšímu vrcholu, který není v jedné ze dvou kapes sousedících s vrcholem zásobníku. Poté, dokud horní dva vrcholy zásobníku spolu s tímto novým vrcholem nejsou v konvexní poloze, vysune zásobník a nakonec nový vrchol do zásobníku vloží. Když procházení ve směru hodinových ručiček dosáhne výchozího bodu, algoritmus vrátí posloupnost vrcholů zásobníku jako trup.
.