Kombinatorisen laskennallisen geometrian tutkimuksen päätavoitteena on kehittää tehokkaita algoritmeja ja tietorakenteita sellaisten ongelmien ratkaisemiseksi, jotka on esitetty geometristen perusobjektien, kuten pisteiden, viivasegmenttien, monikulmioiden, polygonien, moniulotteisten moniulotteisten kuvioiden jne. avulla.
Jotkut näistä ongelmista tuntuvat niin yksinkertaisilta, ettei niitä pidetty ongelmina ennen tietokoneiden tuloa lainkaan. Ajatellaanpa esimerkiksi lähimmän parin ongelmaa:
- Jos tasossa on n pistettä, etsi ne kaksi, joiden etäisyys toisistaan on pienin.
Voidaan laskea kaikkien pisteparien, joita on n(n-1)/2, väliset etäisyydet ja valita sitten se pari, jonka etäisyys on pienin. Tämä raakavoima-algoritmi vie O(n2) aikaa, eli sen suoritusaika on verrannollinen pisteiden lukumäärän neliöön. Klassinen tulos laskennallisessa geometriassa oli algoritmin muotoilu, joka vie aikaa O(n log n). On myös löydetty satunnaistettuja algoritmeja, jotka vievät O(n) odotettua aikaa, sekä deterministinen algoritmi, joka vie O(n log log n) aikaa.
OngelmaluokatEdit
Laskennallisen geometrian keskeiset ongelmat voidaan luokitella eri tavoin eri kriteerien mukaan. Seuraavat yleiset luokat voidaan erottaa toisistaan.
Staattiset ongelmatEdit
Tämän luokan ongelmissa annetaan jokin syötetieto, jota vastaava tuotos pitää konstruoida tai löytää. Joitakin perustavanlaatuisia tämän tyyppisiä ongelmia ovat:
- Kupera runko: Annettuna pistejoukko, etsi pienin kaikki pisteet sisältävä kupera monitahokas monitahokas/polygoni.
- Linjasegmenttien leikkaus: Etsi annetun joukon viivasegmenttien leikkauspisteet.
- Delaunayn kolmiomittaus
- Voronoi-diagrammi: Annettuna joukko pisteitä, jaa avaruus sen mukaan, mitkä pisteet ovat lähimpänä annettuja pisteitä.
- Lineaarinen ohjelmointi
- Lähin pistepari: Annettuna joukko pisteitä, etsi ne kaksi, joiden etäisyys toisistaan on pienin.
- Kaukaisin pistepari
- Suurin tyhjä ympyrä: Annettuna joukko pisteitä, löydä suurin ympyrä, jonka keskipiste on niiden kuperan rungon sisällä ja joka ei sulje sisäänsä yhtäkään niistä.
- Euklidinen lyhin polku: Yhdistä kaksi pistettä euklidisessa avaruudessa (jossa on polyedrisiä esteitä) lyhimmällä polulla.
- Polygonikolmio: Annettuna monikulmio, jaa sen sisus kolmioiksi
- Verkon tuottaminen
- Boolen operaatiot monikulmioille
Tämän ongelmaluokan laskennallinen monimutkaisuus arvioidaan ajan ja tilan (tietokoneen muistin) perusteella, joka tarvitaan tietyn ongelman ratkaisemiseen.
Geometriset kyselyongelmatEdit
Geometrisissä kyselyongelmissa, jotka tunnetaan yleisesti geometrisina hakuongelmina, syöte koostuu kahdesta osasta: hakuavaruusosasta ja kyselyosasta, joka vaihtelee ongelmainstanssien mukaan. Hakuavaruus on tyypillisesti esikäsiteltävä siten, että useisiin kyselyihin voidaan vastata tehokkaasti.
Joitakin perustavanlaatuisia geometrisia kyselyongelmia ovat:
- Alueen haku: Esikäsitellään pistejoukko, jotta voidaan tehokkaasti laskea kyselyalueen sisällä olevien pisteiden määrä.
- Pisteiden paikannus: Kun avaruus on jaettu soluihin, tuotetaan tietorakenne, joka kertoo tehokkaasti, missä solussa kyselypiste sijaitsee.
- Lähin naapuri: Esikäsittele pistejoukko, jotta löydät tehokkaasti, mikä piste on lähimpänä kyselypistettä.
- Säteen jäljittäminen: Kun annetaan joukko kohteita avaruudessa, tuotetaan tietorakenne, joka kertoo tehokkaasti, minkä kohteen kyselysäde leikkaa ensimmäisenä.
Jos hakuavaruus on kiinteä, tämän luokan ongelmien laskennallinen monimutkaisuus arvioidaan yleensä:
- aikana ja tilana, joka tarvitaan haettavan tietorakenteen konstruoimiseen
- aikana (ja joskus ylimääräisenä tilana) kyselyihin vastaamiseen.
Tapauksesta, jossa hakuavaruuden annetaan vaihdella, ks. kohta ”Dynaamiset ongelmat”.
Dynaamiset ongelmatMuokkaa
Toinen suuri luokka ovat dynaamiset ongelmat, joissa tavoitteena on löytää tehokas algoritmi ratkaisun etsimiseen toistuvasti jokaisen syöttötiedon inkrementaalisen muutoksen jälkeen (lisäys tai poisto syöttögeometristen elementtien lisäämistä tai poistamista). Tämäntyyppisten ongelmien algoritmit sisältävät tyypillisesti dynaamisia tietorakenteita. Mikä tahansa laskennallinen geometrinen ongelma voidaan muuntaa dynaamiseksi ongelmaksi, mutta käsittelyaika kasvaa. Esimerkiksi alueen hakuongelma voidaan muuntaa dynaamiseksi alueen hakuongelmaksi mahdollistamalla pisteiden lisääminen ja/tai poistaminen. Dynaamisen koveran rungon ongelman tarkoituksena on seurata koveraa runkoa esimerkiksi dynaamisesti muuttuvalle pistejoukolle, ts, kun syöttöpisteitä lisätään tai poistetaan.
Tämän ongelmaluokan laskennallista monimutkaisuutta arvioidaan:
- aikana ja tilana, joka tarvitaan haettavan tietorakenteen rakentamiseen
- aikana ja tilana, joka tarvitaan haetun tietorakenteen muokkaamiseen sen jälkeen, kun hakuavaruus on muuttunut inkrementaalisesti
- aikana (ja joskus ylimääräisenä tilana), joka kuluu kyselyyn vastaamiseen.
VariaatiotEdit
Joitakin ongelmia voidaan kontekstista riippuen käsitellä jompaankumpaan kategoriaan kuuluvina. Tarkastellaan esimerkiksi seuraavaa ongelmaa.
- Polygonin piste: Päätä, onko piste tietyn monikulmion sisällä vai ulkopuolella.
Monissa sovelluksissa tätä ongelmaa käsitellään kertaluonteisena eli ensimmäiseen luokkaan kuuluvana. Esimerkiksi monissa tietokonegrafiikan sovelluksissa yleinen ongelma on selvittää, mitä aluetta näytöllä napsautetaan osoittimella. Joissakin sovelluksissa kyseinen monikulmio on kuitenkin muuttumaton, kun taas piste edustaa kyselyä. Esimerkiksi syötetty monikulmio voi edustaa maan rajaa ja piste on lentokoneen sijainti, ja ongelmana on määrittää, rikkoiko lentokone rajaa. Lopuksi, kuten aiemmin mainitussa tietokonegrafiikan esimerkissä, CAD-sovelluksissa muuttuvat syöttötiedot tallennetaan usein dynaamisiin tietorakenteisiin, joita voidaan hyödyntää piste-polygoni-kyselyjen nopeuttamiseksi.
Joissakin kyselyongelmien yhteyksissä on olemassa kohtuullisia odotuksia kyselyjen järjestyksestä, joita voidaan hyödyntää joko tehokkaiden tietorakenteiden tai tiukempien laskennallisen monimutkaisuuden estimaattien saamiseksi. Joissakin tapauksissa on esimerkiksi tärkeää tietää pahin mahdollinen kokonaisaika koko N kyselyn sarjalle eikä yksittäiselle kyselylle. Katso myös ”amortized analysis”.