A számítási geometria a számítástechnika azon ága, amely a geometriai fogalmakkal leírható algoritmusok tanulmányozásával foglalkozik. Néhány tisztán geometriai probléma maguknak a számítási geometriai algoritmusoknak a vizsgálatából ered, és az ilyen problémákat is a számítási geometria részének tekintik. Bár a modern számítási geometria viszonylag új keletű fejlesztés, a számítástechnika egyik legrégebbi területe, amelynek története egészen az ókorig nyúlik vissza.
A számítási komplexitás központi jelentőségű a számítási geometriában, és hatalmas gyakorlati relevanciával bír, ha az algoritmusokat rendkívül nagy – akár több tíz- vagy százmillió pontot tartalmazó – adathalmazokon alkalmazzák. Az ilyen halmazok esetében az O (n²) és közötti napok és másodpercek közötti eltérést jelenthet a számítási időben.
A számítógépes geometria, mint önálló tudományág fejlődésének fő hajtóerejét a számítógépes grafika, valamint a számítógéppel támogatott tervezés és gyártás (CAD/CAM) terén elért haladás jelentette, de a számítási geometria számos problémája természetéből adódóan klasszikus, és a matematikai vizualizációból is származhat.
A számítógépes geometria további fontos alkalmazási területei közé tartozik a robotika (mozgástervezés és láthatósági problémák), a földrajzi információs rendszerek (GIS) (geometriai helymeghatározás és keresés, útvonaltervezés), az integrált áramkör-tervezés (IC geometria tervezése és ellenőrzése), a számítógéppel támogatott mérnöki munka (CAE) (hálógenerálás) és a számítógépes látás (3D rekonstrukció).
A számítógépes geometria főbb ágai a következők:
A kombinatorikus számítási geometria, más néven algoritmikus geometria, amely a geometriai objektumokat diszkrét entitásokként kezeli. Preparata és Shamos témában írt alapműve a „számítási geometria” kifejezés ebben az értelemben vett első használatát 1975-re teszi. A numerikus számítási geometria, más néven gépi geometria, számítógéppel támogatott geometriai tervezés (CAGD) vagy geometriai modellezés, amely elsősorban a valós világ objektumainak olyan formában történő reprezentációjával foglalkozik, amely alkalmas a CAD/CAM rendszerekben végzett számítógépes számításokra. Ez az ág az ábrázoló geometria továbbfejlesztéseként is felfogható, és gyakran a számítógépes grafika vagy a CAD egyik ágának tekintik. A „számítási geometria” kifejezés ebben a jelentésben 1971 óta használatos.
Bár a számítógépes geometria legtöbb algoritmusát elektronikus számítógépekre fejlesztették ki (és fejlesztik jelenleg is), néhány algoritmust nem hagyományos számítógépekre (pl. optikai számítógépekre) terveztek.
Kombinatorikus számítási geometria A kombinatorikus számítógépes geometria kutatásának elsődleges célja olyan hatékony algoritmusok és adatstruktúrák kidolgozása, amelyek a geometriai alapobjektumokkal – például pontokkal, szakaszokkal, sokszögekkel, poliéderekkel stb. – megfogalmazott problémák megoldására szolgálnak.
Ezen problémák némelyike annyira egyszerűnek tűnik, hogy a számítógépek megjelenéséig egyáltalán nem is tekintették őket valódi problémának. Vegyük például a legközelebbi pontpár problémát:
Adott n darab pont a síkon. Keressük meg azt a két pontot, amelyek a legkisebb távolságra vannak egymástól.
Kiszámíthatnánk a távolságot az összes pontpár között, amelyekből összesen létezik, majd kiválaszthatnánk a legkisebb távolsággal rendelkező párt. Ez a nyers erőre épülő algoritmus O (n²) időt vesz igénybe; azaz a végrehajtási ideje a pontok számának négyzetével arányos. A számítási geometria egyik klasszikus eredménye egy olyan algoritmus megfogalmazása volt, amely mindössze időt vesz igénybe. Azóta olyan randomizált algoritmusokat is felfedeztek, amelyek O (n) várható időt vesznek igénybe , valamint egy determinisztikus algoritmust is, amelynek futásideje .
Főbb problémák A számítási geometria alapvető problémái különböző kritériumok alapján, többféle módon is osztályozhatók. Általánosságban a következő főbb problémaosztályokat különböztethetjük meg.
Statikus probléma Az ebbe a kategóriába tartozó problémák esetében adott valamilyen bemenet (input), és az annak megfelelő kimenetet (output) kell előállítani vagy megkeresni. Néhány ilyen típusú alapvető probléma a következő:
Konvex burok (convex hull): Adott egy pontkészlet, keressük meg azt a legkisebb konvex poliédert/sokszöget, amely a halmaz összes pontját tartalmazza. Szakasz metszéspontja: Keressük meg a metszéspontokat egy adott egyenes szakaszokból álló halmaz elemei között. Delaunay-háromszögelés Voronoi-diagram: Adott ponthalmaz esetén bontsuk fel a teret aszerint, hogy mely pontok vannak a legközelebb az adott pontokhoz. Lineáris programozás Legközelebbi pontpár: Adott egy pontkészlet, keressük meg azt a két pontot, amelyek a legkisebb távolságra vannak egymástól. Legtávolabbi pontpár Legnagyobb üres kör: Adott egy pontkészlet, keressük meg azt a legnagyobb kört, amelynek középpontja a pontok konvex burkán belül van, és a halmaz egyetlen pontját sem tartalmazza. Euklideszi legrövidebb út: Kössünk össze két pontot egy (poliéder alakú akadályokkal teli) euklideszi térben a legrövidebb úton. Sokszög háromszögelése: Adott egy sokszög, osszuk fel a belső területét háromszögekre. Hálógenerálás Logikai-műveletek poligonokon
Az ebbe a problémacsoportba tartozó feladatok számítási komplexitását az adott problémapéldány megoldásához szükséges idő és tárhely (számítógépes memória) alapján becsülik meg.
Geometriai lekérdezési problémák A geometriai lekérdezési problémákban – amelyeket általában geometriai keresési problémákként is ismernek – a bemenet két részből áll: a keresési térből és a lekérdezési részből, amely a különböző problémapéldányok szerint változik. A keresési teret jellemzően elő kell feldolgozni (preprocessing) olyan módon, hogy a többszörös lekérdezésekre hatékonyan lehessen választ adni.
Néhány alapvető geometriai lekérdezési probléma:
Tartománykeresés: Egy pontkészlet előfeldolgozása annak érdekében, hogy hatékonyan megszámolható vagy kigyűjthető legyen a lekérdezési régión belüli pontok száma. Pontelhelyezési probléma: A tér cellákra történő felosztása alapján egy olyan adatstruktúra létrehozása, amely hatékonyan megmondja, hogy egy lekérdezett pont melyik cellában található. Legközelebbi szomszéd: Egy pontkészlet előfeldolgozása annak érdekében, hogy hatékonyan megtalálható legyen, melyik pont van a legközelebb egy lekérdezett ponthoz. Sugárkövetés: A térben lévő objektumok egy halmaza alapján egy olyan adatstruktúra létrehozá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, az ebbe a kategóriába tartozó problémák számítási komplexitását általában a következőképpen becsülik meg:
a keresendő adatstruktúra felépítéséhez szükséges idő és tárhely (memória); a lekérdezések megválaszolásához szükséges idő (és esetenként plusz tárhely).
Dinamikus problémák Egy másik fő osztályt a dinamikus problémák alkotják, amelyekben a cél egy olyan hatékony algoritmus kidolgozása, amely a bemeneti adatok minden egyes inkrementális (lépésenkénti) módosítása – például geometriai elemek hozzáadása vagy törlése – után képes ismételten megtalálni a megoldást. Az ilyen típusú problémák megoldására szolgáló algoritmusok jellemzően dinamikus adatszerkezeteket alkalmaznak. Bármely számítási geometriai probléma átalakítható dinamikus problémává, a megnövekedett feldolgozási idő árán. Például a tartománykeresési probléma átalakítható dinamikus tartománykeresésiproblémává a pontok hozzáadásának és/vagy törlésének biztosításával. A dinamikus konvex burok probléma lényege a konvex burok nyomon követése egy dinamikusan változó pontkészlet esetében, azaz mialatt a bemeneti pontokat beillesztik vagy törlik.
Az ebbe a problémacsoportba tartozó feladatok számítási komplexitását a következők alapján becsülik meg:
a keresendő adatstruktúra felépítéséhez szükséges idő és tárhely (memória); a keresendő adatstruktúra módosításához szükséges idő és tárhely, a keresési tér inkrementális (lépésenkénti) változása után; a lekérdezések megválaszolásához szükséges idő (és esetenként plusz tárhely).
Variációk Egyes problémák – a kontextustól függően – bármelyik kategóriába tartozóként kezelhetők. Tekintsük példaként a következő problémát:
Pont a sokszögben: Döntsük el, hogy egy adott pont egy megadott sokszögön belül vagy kívül helyezkedik-e el.
Számos alkalmazásban ezt a problémát egyszeri (single-shot) feladatként kezelik, vagyis az első osztályba tartozónak tekintik. A számítógépes grafika számos területén például gyakori probléma annak meghatározása, hogy a képernyő melyik területére kattintottak a mutatóval (egérrel). Egyes alkalmazásokban azonban a szóban forgó sokszög változatlan, míg a pont egy lekérdezést testesít meg. A bemeneti sokszög reprezentálhatja például egy ország határát, a pont pedig egy repülőgép pozícióját, a feladat pedig annak eldöntése, hogy a repülőgép megsértette-e a határt. Végezetül, a számítógépes grafika korábban említett példájánál maradva, a CAD alkalmazásokban (számítógéppel támogatott tervezésben) a változó bemeneti adatokat gyakran dinamikus adatstruktúrákban tárolják, ami jól kihasználható a pont-a-sokszögben lekérdezések felgyorsítására.
A lekérdezési problémák bizonyos kontextusaiban észszerű elvárások fogalmazhatók meg a lekérdezések sorrendjére vonatkozóan, ami kihasználható hatékonyabb adatstruktúrák tervezésére, vagy akár szorosabb számítási komplexitás-becslésekre is. Egyes esetekben például fontosabb a teljes, N darab lekérdezésből álló sorozat végrehajtásához szükséges teljes idő legrosszabb esetét (worst case) ismerni, mint egyetlen önálló lekérdezését. Lásd még: Amortizált elemzés.
Numerikus számítási geometria Ez az ág geometriai modellezésként és számítógéppel támogatott geometriai tervezésként (CAGD) is ismert.
A központi problémaköröket a görbék és felületek modellezése, valamint azok reprezentációja (számítógépes ábrázolása) jelentik.
A legfontosabb eszközök itt a parametrikus görbék és a parametrikus felületek, mint például a Bézier-görbék, a spline-görbék és felületek. Egy fontos nem paraméteres megközelítés a szintvonalas módszer.
A számítógépes geometria alkalmazási területei közé tartozik a hajógyártás, a repülőgépgyártás és az autóipar.
Jegyzetek
Fordítás
További olvasmányok
Számítógépes geometriával foglalkozó könyvek listája
Folyóiratok
Kombinatorikus/algoritmikus számítási geometria Az alábbiakban a geometriai algoritmusokkal kapcsolatos kutatásokat publikáló főbb folyóiratok listája található. Felhívjuk a figyelmet arra, hogy a kifejezetten számítógépes geometriával foglalkozó folyóiratok megjelenésével csökkent a geometriai publikációk aránya az általános célú számítástechnikai és számítógépes grafikai folyóiratokban.
ACM számítástechnikai felmérések ACM tranzakciók grafikákon Acta Informatica Geometria fejlődése Algorithmica Ars Combinatoria Számítógépes geometria: Elmélet és alkalmazások Az ACM közleményei Számítógéppel segített geometriai tervezés Számítógépes grafika és alkalmazások Számítógépes grafika világa Számítástechnika a geometriában és topológiában Diszkrét és számítási geometria Geombinatorika Geometriae Dedicata IEEE Grafikai tranzakciók IEEE tranzakciók számítógépeken IEEE Tranzakciók a Mintaelemzésről és a Gépi Intelligencia Információfeldolgozó levelek Nemzetközi Számítógépes Geometria és Alkalmazások Folyóirata Kombinatorikus Elmélet folyóirat, B sorozat Számítógépes Geometria Folyóirata Differenciálgeometria folyóirat Az ACM folyóirata Algoritmusok folyóirata Számítástechnikai és Rendszertudományi Folyóirat Menedzsmenttudomány Mintafelismerés Mintafelismerő betűk SIAM Számítástechnikai Folyóirat SIGACT Hírek; Joseph O'Rourke "Számítástechnikai geometria rovata" Elméleti számítástechnika A vizuális számítógép
További információk
Számítógépes geometria Számítógépes geometria oldalak Geometria a gyakorlatban