Tarkastellaan yleistä tapausta, jossa algoritmin syötteenä on äärellinen järjestämätön joukko kartesiolaisen tason pisteitä. Tärkeä erikoistapaus, jossa pisteet annetaan yksinkertaisen monikulmion rajan läpikulkujärjestyksessä, kuvataan myöhemmin erillisessä alaluvussa.
Jos kaikki pisteet eivät ole samalla suoralla, niin niiden kovera runko on kovera monikulmio, jonka kärkipisteet ovat joitakin syöttöjoukon pisteitä. Sen yleisin esitys on luettelo sen kärkipisteistä, jotka on järjestetty sen rajaa pitkin myötä- tai vastapäivään. Joissakin sovelluksissa on kätevää esittää kovera monikulmio joukon puolitasojen leikkauspisteenä.
Laskennallisen monimutkaisuuden alarajaEdit
Tasossa olevien pisteiden äärelliselle joukolle koverana monikulmiona esitetyn koveran rungon löytämisen laskennallisen monimutkaisuuden alaraja voidaan helposti osoittaa olevan sama kuin lajittelun tapauksessa seuraavan reduktion avulla. Joukolle x 1 , … , x n {\displaystyle x_{1},\dots ,x_{n}}}
lajiteltavia lukuja tarkastellaan pistejoukkoa ( x 1 , x 1 2 ) , … , ( x n , x n 2 ) {\displaystyle (x_{1},x_{1}^{2}),\pisteet ,(x_{n},x_{n}^{2})}
pisteistä tasossa. Koska ne sijaitsevat paraabelilla, joka on kovera käyrä, on helppo nähdä, että koveran rungon kärkipisteet tuottavat rajaa pitkin kuljettaessa numeroiden x 1 , … , x n lajitellun järjestyksen {\displaystyle x_{1},\dots ,x_{n}}}
. On selvää, että kuvattu lukujen muuttaminen pisteiksi ja sen jälkeen niiden lajitellun järjestyksen poimiminen vaatii lineaarista aikaa. Siksi yleisessä tapauksessa n pisteen kuperaa runkoa ei voida laskea nopeammin kuin lajittelua.
Vakiintunut Ω(n log n)-alarajoitus lajittelulle on todistettu laskennan päätöspuumallissa, jossa voidaan suorittaa vain numeerisia vertailuja mutta ei aritmeettisia operaatioita; tässä mallissa ei kuitenkaan voida lainkaan laskea koveria runkoja. Lajittelu vaatii Ω(n log n)-aikaa myös algebrallisessa päätöspuumallissa, joka soveltuu paremmin koverille rungoille, ja tässä mallissa myös koverat rungot vaativat Ω(n log n)-aikaa. Tietokoneiden aritmeettisissa malleissa, joissa lukuja voidaan lajitella nopeammin kuin O(n log n)-ajassa, esimerkiksi käyttämällä kokonaislukujen lajittelualgoritmeja, tasomaiset koverat rungot voidaan kuitenkin laskea myös nopeammin: Grahamin skannausalgoritmi koverille rungoille koostuu yhdestä lajitteluvaiheesta, jota seuraa lineaarinen määrä lisätyötä.
Optimaaliset ulostuloherkät algoritmitEdit
Kuten edellä todettiin, koveran rungon löytämisen monimutkaisuus syötteen koon n funktiona on alarajoitettu Ω(n log n). Joidenkin kuperan rungon algoritmien monimutkaisuutta voidaan kuitenkin luonnehtia sekä syötekoon n että tuloskoon h (rungon pisteiden lukumäärä) suhteen. Tällaisia algoritmeja kutsutaan ulostuloherkiksi algoritmeiksi. Ne voivat olla asymptoottisesti tehokkaampia kuin Θ(n log n)-algoritmit tapauksissa, joissa h = o(n).
Lähtöherkkien konveksirunkoalgoritmien huonoimman tapauksen käyntiajan alarajan todettiin olevan Ω(n log h) tasomaisessa tapauksessa. On olemassa useita algoritmeja, jotka saavuttavat tämän optimaalisen aikakompleksisuuden. Varhaisimman niistä esittivät Kirkpatrick ja Seidel vuonna 1986 (he kutsuivat sitä ”äärimmäiseksi konveksirunkoalgoritmiksi”). Paljon yksinkertaisemman algoritmin kehitti Chan vuonna 1996, ja sitä kutsutaan Chanin algoritmiksi.
AlgoritmitEdit
Tunnetut kuperan rungon algoritmit on lueteltu alla ensimmäisen julkaisupäivän mukaisessa järjestyksessä. Kunkin algoritmin aikakompleksisuus ilmoitetaan tulopisteiden lukumäärän n ja rungon pisteiden lukumäärän h suhteen. Huomaa, että pahimmassa tapauksessa h voi olla yhtä suuri kuin n.
- Gift wrapping, a.k.a. Jarvisin marssi – O(nh)
Yksi yksinkertaisimmista (vaikkakaan ei pahimmassa tapauksessa aikatehokkaimmista) planaarisista algoritmeista. Luonut itsenäisesti Chand & Kapur vuonna 1970 ja R. A. Jarvis vuonna 1973. Sen aikavaativuus on O(nh), missä n on joukon pisteiden lukumäärä ja h on rungon pisteiden lukumäärä. Pahimmassa tapauksessa monimutkaisuus on Θ(n2). - Graham-skannaus – O(n log n)
Hieman kehittyneempi, mutta paljon tehokkaampi algoritmi, jonka Ronald Graham julkaisi vuonna 1972. Jos pisteet on jo lajiteltu jonkin koordinaatin mukaan tai kulman mukaan kiinteään vektoriin, algoritmi vie O(n) aikaa. - Quickhull
Luotu itsenäisesti vuonna 1977 W. Eddyn ja vuonna 1978 A. Bykatin toimesta. Quicksort-algoritmin tavoin sen odotettu aikakompleksisuus on O(n log n), mutta se voi pahimmassa tapauksessa degeneroitua O(n2):ksi. - Divide and conquer – O(n log n)
Toinen O(n log n)-algoritmi, jonka julkaisivat vuonna 1977 Preparata ja Hong. Tämä algoritmi soveltuu myös kolmiulotteiseen tapaukseen. - Monotoninen ketju eli Andrew’n algoritmi – O(n log n)
Julkaisi vuonna 1979 A. M. Andrew. Algoritmi voidaan nähdä muunnelmana Graham-skannauksesta, joka lajittelee pisteet leksikografisesti niiden koordinaattien mukaan. Kun syöte on jo lajiteltu, algoritmi vie O(n) aikaa. - Inkrementaalinen koveran rungon algoritmi – O(n log n)
Julkaisi vuonna 1984 Michael Kallay. - Kirkpatrick-Seidelin algoritmi – O(n log h)
Ensimmäinen optimaalinen ulostuloherkkä algoritmi. Se muokkaa hajota ja hallitse -algoritmia käyttämällä avioliitto ennen valloitusta -tekniikkaa ja matalaulotteista lineaarista ohjelmointia. Julkaisivat Kirkpatrick ja Seidel vuonna 1986. - Chanin algoritmi – O(n log h)
Yksinkertaisempi optimaalinen tuotosherkkä algoritmi, jonka Chan loi vuonna 1996. Se yhdistää lahjapakkauksen ja O(n log n)-algoritmin (kuten Grahamin skannaus) suorittamisen pienillä syötteen osajoukoilla.
Akl-Toussaint-heuristiikkaEdit
Seuraavaa yksinkertaista heuristiikkaa käytetään usein ensimmäisenä askeleena konveksuaalisen rungon (convex rumpus) algoritmien implementoinneissa niiden suorituskyvyn parantamiseksi. Se perustuu Selim Aklin ja G. T. Toussaintin tehokkaaseen koveran rungon algoritmiin, 1978. Ajatuksena on sulkea nopeasti pois monia pisteitä, jotka eivät kuitenkaan kuuluisi kuperaan runkoon. Menetelmä perustuu seuraavaan ajatukseen. Etsitään kaksi pistettä, joiden x-koordinaatit ovat pienimmät ja suurimmat, sekä kaksi pistettä, joiden y-koordinaatit ovat pienimmät ja suurimmat. (Kukin näistä operaatioista vie aikaa O(n).) Nämä neljä pistettä muodostavat kuperan nelikulmion, ja kaikki tässä nelikulmiossa olevat pisteet (lukuun ottamatta neljää alun perin valittua kärkeä) eivät kuulu kuperaan runkoon. Kaikkien näiden nelikulmion sisällä olevien pisteiden löytäminen on myös O(n), joten koko operaatio on O(n). Vaihtoehtoisesti nelikulmioon voidaan lisätä myös pisteet, joiden x- ja y-koordinaattien summat ovat pienimmät ja suurimmat, sekä pisteet, joiden x- ja y-koordinaattien erotukset ovat pienimmät ja suurimmat, jolloin muodostuu epäsäännöllinen kovera kahdeksankulmio, jonka sisuskalut voidaan turvallisesti hylätä. Jos pisteet ovat satunnaismuuttujia, niin kapealle mutta yleisesti esiintyvälle todennäköisyystiheysfunktioiden luokalle tämä heitteillejättö esikäsittelyvaihe saa kuperan rungon algoritmin toimimaan lineaarisessa odotetussa ajassa, vaikka kuperan rungon algoritmin pahimmassa tapauksessa monimutkaisuus olisi kvadraattinen suhteessa n.
On-line ja dynaamiset kuperan rungon ongelmat Muokkaa
Ylläolevassa keskustelussa tarkastellaan tapausta, jossa kaikki syötepisteet tiedetään ennakolta. Voidaan tarkastella kahta muuta asetelmaa.
- Online-konveksirunko-ongelma: Syöttöpisteet saadaan peräkkäin yksi kerrallaan. Kun jokainen piste on saapunut syötteeseen, on tähän mennessä saadun pistejoukon kovera runko laskettava tehokkaasti.
- Dynaaminen koveran rungon ylläpito: Dynaaminen versio voidaan käsitellä O(log2 n) per operaatio.
Simple polygonEdit
Pääartikkeli: Yksinkertaisen monikulmion kovera kuoriYksinkertaisen monikulmion kovera kuori jaetaan monikulmion mukaan osiin, joista yksi on itse monikulmio ja loput ovat monikulmion reunan palan ja yhden kuoren reunan rajaamia taskuja. Vaikka yksinkertaisen monikulmion koveran rungon rakentamisen ongelmaan on julkaistu monia algoritmeja, lähes puolet niistä on virheellisiä.McCallum ja Avis toimittivat ensimmäisen oikean algoritmin.Graham & Yaon (1983) ja Leen (1983) myöhemmin tekemä yksinkertaistus käyttää vain yhtä pinotietorakennetta. Heidän algoritminsa kulkee monikulmion läpi myötäpäivään aloittaen sen vasemmanpuoleisimmasta kärjestä. Samalla se tallentaa pinoon kuperan sarjan kärkipisteitä, joita ei ole vielä tunnistettu taskujen sisällä oleviksi. Algoritmi seuraa jokaisella askeleella polkua polygonia pitkin pinon yläreunasta seuraavaan pisteeseen, joka ei ole jommassakummassa pinon yläreunan viereisessä taskussa. Sitten, kun pinon kaksi ylintä kärkeä ja tämä uusi kärki eivät ole kuperassa asennossa, se avaa pinon, ennen kuin se lopulta työntää uuden kärkipisteen pinoon. Kun myötäpäivään kulkeva kierto saavuttaa lähtöpisteen, algoritmi palauttaa pinon kärkipisteiden sarjan rungoksi.