Geometria konputazional

Zilindro baten irudikapen konputazionala.

Geometria konputazionala geometriaren bidez adieraz daitezkeen algoritmoak aztertzen duen informatikaren adarra da. Algoritmo geometriko konputazionalak aztertzean, geometriazko problemak agertzen dira eta problema horiek geometria konputazionalaren zati gisa ere hartzen dira. Geometria konputazional modernoa oraintsuko garapena den arren, konputazioaren eremurik antzinakoenetako bat da.

Konplexutasun konputazionala funtsezkoa da geometria konputazionalean, garrantzi praktiko handikoarekin algoritmoak hamarnaka edo ehunka milioi datu multzoekin erabiltzen badira. Datu multzo horietarako bi ebazpen desberdinen arteko diferentzia, kalkuluko segundoen eta egunen arteko diferentzia bezalakoa izan daiteke.

Geometria konputazionala diziplina bezala garatzeko bultzada nagusia ordenagailu bidezko grafikoen eta ordenagailuz lagundutako diseinuaren eta fabrikazioaren (CADきゃど/CAM) aurrerapenak izan ziren. Hala eta guztiz ere, geometria konputazionalaren problema asko naturan aurkitzen dira, eta bistaratze matematikotik etor daitezke.

Beste aplikazio garrantzitsuen artean hauek daude:

Robotika: mugimenduaren plangintza eta ikuspen arazoak.

Informazio geografikoko sistemak (GIS ingelesez): kokapen geografikoa eta bilaketa, bide plangintza.

Zirkuitu integratuen diseinua: zirkuitu integratuen diseinu geometrikoa eta egiaztapena.
Ordenagailuz lagundutako ingeniaritza (CAE ingelesez): sareen sorrera.
Ikusmen artifiziala: 3D berreraikuntza.

Geometria konputazionalaren adar nagusiak dira:

Konbinazioko geometria konputazionalak, geometria algoritmikoa ere deitua, objetu geometrikoak entitate diskretu gisa lantzen ditu.^[1]
Zenbakizko geometria konputazionalak, makina geometria, ordenagailuz lagundutako diseinu geometrikoa (CAGD ingelesez) edo modelatze geometrikoa ere deitua, CADきゃど/CAM sistemetan mundu errealeko objetuak konputazio informatikoetarako egokiak diren formetaz irudikatzeaz arduratzen da. Adar hau, geometria deskribatzailearen garapen bezala ikus daiteke, eta, sarri, ordenagailu bidezko grafikoen edo CADaren adar gisa hartzen da.^[2]

Konbinazioko geometria konputazional

Konbinazioko geometria konputazionalaren ikerketaren helburu nagusia algoritmo eta datu egitura eraginkorrak garatzea da, oinarrizko objetu geometrikoei (puntuak, lerro segmentuak, poligonoak, poliedroak, eta abar) buruz adierazitako problemak ebazteko.

Arazo horietako batzuk hain sinpleak dirudite, ordenagailuak iritsi arte ez zirela batere arazo gisa hartzen. Demagun, adibidez, Bikote hurbileneko problema:

Planoan n puntu emanda, elkarrengandik distantzia txikiena duten biak aurkitu.

Puntu pare guztien arteko distantziak kalkula litezke, n(n-1)/2 aldiz, eta gero distantzia txikiena duen bikotea hautatu. Indar basatiko algoritmo honek O(n²) denbora behar du; hau da, bere exekuzio denbora puntu kopuruaren karraturekiko proportzionala da. Geometria konputazionalaren emaitza klasikoa O(n log n) hartzen duen algoritmoaren formulazioa izan zen. O(n) hartzen duten ausazko algoritmoak^[3] eta O(n log log n) hartzen duten algoritmo deterministak^[4] ere aurkitu dira.

Arazo kasuak

Geometria konputazionalaren oinarrizko arazoak modu desberdinetan sailka daitezke, hainbat irizpideren arabera. Honako klase orokorrak bereiz daitezke:

Problema estatikoak
Galdera geometrikoen problemak
Problema dinamikoak
Aldaketak

Zenbakizko geometria konputazional

Adar hau modelatze geometriko eta ordenagailuz lagundutako diseinu geometriko (CAGD) izenekin ere ezagutzen da.

Funtsezko problemak kurben eta gainzalen modelatzea eta irudikapena dira.

Instrumentu garrantzitsuenak kurba parametrikoak eta gainazal parametrikoak dira, hala nola Bézier kurbak eta spline kurbak eta gainazalak. Ikuspegi ez-parametriko garratzitsu bat maila-multzoaren metodoa da.

Geometria konputazionalaren aplikazio-eremuak ontzigintzako, aeronautikako eta automobileko industriak dira.

Erreferentziak

↑ (Ingelesez) Franco P. Preparata eta Michael Ian Shamos. (1985). Computational Geometry - An Introduction. Springer-Verlag ISBN 0-387-96131-3..
↑ (Ingelesez) A.R. Forrest. (1971). "Computational geometry". Proc. Royal Society London, 321, series 4, 187-195 or..
↑ (Ingelesez) S. Khuller and Y. Matias. (1995). A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1), 34—37 or..
↑ (Ingelesez) S. Fortune and J.E. Hopcroft. (1979). "A note on Rabin's nearest-neighbor algorithm.". Information Processing Letters, 8(1), 20-23 or..

Kanpo estekak

Datuak: Q874709
Multimedia: Computational geometry / Q874709

[1] (Ingelesez) Franco P. Preparata eta Michael Ian Shamos. (1985). Computational Geometry - An Introduction. Springer-Verlag ISBN 0-387-96131-3..

[2] (Ingelesez) A.R. Forrest. (1971). "Computational geometry". Proc. Royal Society London, 321, series 4, 187-195 or..

[3] (Ingelesez) S. Khuller and Y. Matias. (1995). A simple randomized sieve algorithm for the closest-pair problem. Inf. Comput., 118(1), 34—37 or..

[4] (Ingelesez) S. Fortune and J.E. Hopcroft. (1979). "A note on Rabin's nearest-neighbor algorithm.". Information Processing Letters, 8(1), 20-23 or..

[1]

[2]

[3]

[4]