geometria computazionale
Indice
La geometria computazionale è una branca della geometria che studia gli algoritmi efficienti per la soluzione di problemi di natura geometrica, e la loro implementazione. Il termine è stato coniato nel 1969 da Minsky e Papert nel saggio Perceptron, ma è stato usato per la prima volta con il significato corrente nella tesi di dottorato di Ian Shamos Problems in Computational Geometry (1975). Si tratta di una disciplina recente che usa i risultati di altre discipline, come l’algebra lineare, la topologia e la geometria combinatoria (in particolare la teoria dei grafi). Un algoritmo efficiente ha una bassa complessità computazionale, cioè impegna la minore quantità di risorse possibili in termini di tempo impiegato e di spazio di memoria occupata in funzione della dimensione del problema. L’impiego di algoritmi esatti o efficienti esclude le divisioni e le operazioni trigonometriche, che sono affette da errori di arrotondamento (e sono computazionalmente onerose). I principali rami della geometria computazionale sono: la g. computazionale combinatoria, detta algoritmica, che affronta oggetti geometrici come entità distinte; la g. computazionale numerica, detta geometria macchina; il progetto geometrico assistito da computer (CAGD) o modellamento geometrico, che affronta originalmente la rappresentazione di oggetti di mondo reale in forme adatte per calcoli di computer in sistemi di CAD/CAMMA. Tra i campi di applicazione della geometria computazionale si segnalano: la robotica, i Sistemi Geografici Informativi (GIS), la computer grafica, la logistica. Tra i problemi risolvibili con la geometria computazionale: inviluppo convesso; diagramma di Voronoi; triangolazione; programmazione lineare; cammino minimo e localizzazione di punti.
Bibliografia
M. Minsky, S. Papert, Perceptrons. An introduction to computational geometry, Cambridge 1969; J.R. Sack, J. Urrutia, Handbook of Computational Geometry, Amsterdam 2000; G. Narasimhan, M. Smid, Geometric Spanner Networks, Cambridge 2007; S. Kumar Ghosh, Visibility Algorithms in the Plane, Cambridge 2007; S. L. Devadoss, J. O’Rourke Discrete and Computational Geometry, Princeton 2011.