A kombinatorikus számítógépes geometria kutatásának elsődleges célja, hogy hatékony algoritmusokat és adatstruktúrákat dolgozzon ki az alapvető geometriai objektumok – pontok, vonalszakaszok, sokszögek, poliéderek stb. – által meghatározott problémák megoldására.
Egy részük olyan egyszerűnek tűnik, hogy a számítógépek megjelenéséig egyáltalán nem is tekintették őket problémának. Vegyük például a Legközelebbi pár problémát:
- Adott n pont a síkon, találjuk meg azt a kettőt, amelyik a legkisebb távolságra van egymástól.
Az összes pontpár – amelyekből n(n-1)/2 van – közötti távolságot kiszámíthatjuk, majd kiválaszthatjuk a legkisebb távolsággal rendelkező párt. Ez a nyers erővel végrehajtott algoritmus O(n2) időt vesz igénybe, azaz a végrehajtási ideje arányos a pontok számának négyzetével. A számítási geometria klasszikus eredménye volt egy olyan algoritmus megfogalmazása, amely O(n log n) időt vesz igénybe. Felfedeztek olyan véletlenszerű algoritmusokat is, amelyek O(n) várható időt vesznek igénybe, valamint olyan determinisztikus algoritmust, amely O(n log log n) időt vesz igénybe.
ProblémaosztályokSzerkesztés
A számítási geometria alapvető problémái különböző szempontok szerint többféleképpen osztályozhatók. A következő általános osztályokat különböztethetjük meg.
Statikus problémákSzerkesztés
Az ebbe a kategóriába tartozó problémáknál valamilyen bemenetet adunk meg, és a megfelelő kimenetet kell megkonstruálni vagy megtalálni. Néhány alapvető ilyen típusú probléma:
- Konvex héj: Adott egy ponthalmaz, találjuk meg az összes pontot tartalmazó legkisebb konvex poliédert/poligont.
- Vonalszakaszok metszése: Adott vonalszakaszok metszéspontjainak megkeresése.
- Delaunay-trianguláció
- Voronoi-diagram: Adott ponthalmaz esetén osszuk fel a teret aszerint, hogy mely pontok vannak a legközelebb az adott pontokhoz.
- Lineáris programozás
- Legközelebbi pontpár: Adott ponthalmazból keresse meg azt a kettőt, amelyek a legkisebb távolságra vannak egymástól.
- Távolabbi pontpár
- Legnagyobb üres kör: Adott egy ponthalmaz, találjuk meg a legnagyobb kört, amelynek középpontja a konvex burkon belül van, és egyiket sem zárja be.
- Euklideszi legrövidebb út: Két pont összekötése egy euklideszi térben (poliéderes akadályokkal) a legrövidebb úttal.
- Poligon-trianguláció: Adott egy sokszög, osszuk fel a belsejét háromszögekre
- Hálógenerálás
- Boolean műveletek sokszögeken
A problémák ezen osztályának számítási komplexitását egy adott problémapéldány megoldásához szükséges idő és hely (számítógépes memória) alapján becsüljük.
Geometriai lekérdezési problémákSzerkesztés
A geometriai lekérdezési problémákban, közismert nevükön geometriai keresési problémákban a bemenet két részből áll: a keresési térrészből és a lekérdezési részből, amely a problémapéldányokon keresztül változik. A keresési teret általában előfeldolgozásra van szükség, oly módon, hogy több lekérdezés is hatékonyan megválaszolható legyen.
Néhány alapvető geometriai lekérdezési probléma:
- Tartománykeresés: Egy ponthalmaz előfeldolgozása annak érdekében, hogy hatékonyan megszámoljuk a lekérdezési tartományon belüli pontok számát.
- Pontmeghatározás: A tér cellákra való felosztása esetén olyan adatszerkezet előállítása, amely hatékonyan megmondja, hogy egy lekérdezési pont melyik cellában található.
- Legközelebbi szomszéd: Pontok halmazának előfeldolgozása annak érdekében, hogy hatékonyan meg lehessen találni, melyik pont van a legközelebb egy lekérdezési ponthoz.
- Sugárkövetés: Adott térbeli objektumhalmaz esetén olyan adatszerkezet előállítása, amely hatékonyan megmondja, hogy egy lekérdezési sugár melyik objektumot metszi először.
Ha a keresési tér rögzített, a problémák ezen osztályának számítási bonyolultságát általában a következőkkel becsüljük:
- a keresendő adatszerkezet felépítéséhez szükséges idő és tér
- a lekérdezések megválaszolásához szükséges idő (és néha egy extra tér).
Azt az esetet, amikor a keresési tér változhat, lásd “Dinamikus problémák”.
Dinamikus problémákSzerkesztés
Még egy másik nagy osztály a dinamikus problémák, amelyekben a cél egy hatékony algoritmus megtalálása a megoldás ismételt megtalálására a bemeneti adatok minden egyes inkrementális módosítása (bemeneti geometriai elemek hozzáadása vagy törlése) után. Az ilyen típusú problémák algoritmusai jellemzően dinamikus adatszerkezeteket tartalmaznak. Bármely számítási geometriai probléma dinamikussá alakítható, a megnövekedett feldolgozási idő árán. Például a tartománykeresési probléma átalakítható dinamikus tartománykeresési problémává a pontok hozzáadásának és/vagy törlésének biztosításával. A dinamikus konvex burkolat probléma a konvex burkolat nyomon követése, pl. a dinamikusan változó ponthalmazhoz, azaz, miközben a bemeneti pontok beillesztésre vagy törlésre kerülnek.
A problémák ezen osztályának számítási bonyolultságát a következőkkel becsüljük:
- a keresendő adatstruktúra felépítéséhez szükséges idő és tér
- a keresett adatstruktúra módosításához szükséges idő és tér a keresési tér inkrementális változása után
- a lekérdezés megválaszolásához szükséges idő (és néha egy extra tér).
VariációkSzerkesztés
A kontextustól függően egyes problémák bármelyik kategóriába tartozónak tekinthetők. Vegyük például a következő problémát.
- Pont a sokszögben: Döntsük el, hogy egy pont egy adott sokszögön belül vagy kívül van-e.
Ezt a problémát számos alkalmazásban egyfeles problémaként kezeljük, azaz az első osztályba tartozik. Például a számítógépes grafika számos alkalmazásában gyakori probléma, hogy meg kell találni, hogy a képernyőn melyik területre kattint egy mutató. Egyes alkalmazásokban azonban a kérdéses sokszög invariáns, míg a pont egy lekérdezést jelent. Például a bemeneti poligon egy ország határát ábrázolhatja, a pont pedig egy repülőgép helyzetét, és a probléma annak meghatározása, hogy a repülőgép megsértette-e a határt. Végül, a korábban említett számítógépes grafikai példában, a CAD-alkalmazásokban a változó bemeneti adatokat gyakran dinamikus adatstruktúrákban tárolják, ami kihasználható a pont a poligonban lekérdezések gyorsítására.
A lekérdezési problémák egyes kontextusaiban ésszerű elvárások vannak a lekérdezések sorrendjére vonatkozóan, ami kihasználható akár hatékony adatstruktúrák, akár szorosabb számítási bonyolultsági becslések érdekében. Bizonyos esetekben például fontos, hogy ne egyetlen lekérdezésre, hanem N lekérdezés teljes sorozatának teljes idejére vonatkozóan ismerjük a legrosszabb esetet. Lásd még “amortizált elemzés”.