geometria computazionale

La geometria computazionale è la branca della geometria che studia gli algoritmi efficienti per la soluzione di problemi di natura geometrica, e la loro implementazione informatica al calcolatore. Per "algoritmo efficiente" si intende un algoritmo che ha una bassa complessità computazionale, cioè che impegna la minore quantità di risorse possibili in termini di tempo impiegato e di spazio di memoria occupata in funzione della dimensione del problema. Per "algoritmo esatto" si intende un algoritmo che, mediante l'uso di apposite tecniche, eviti le operazioni computazionalmente a rischio di errori di arrotondamento (in special modo le divisioni e le funzioni trigonometriche). Sebbene la Geometria computazionale sia una disciplina relativamente recente, essa utilizza risultati di molti altri campi della Matematica, quali l'algebra lineare, la topologia e la geometria combinatoria (in special modo la teoria dei grafi). Il nome Geometria computazionale è stato coniato da Marvin Minsky nel suo libro Perceptrons, ma è stato usato per la prima volta col significato corrente nella tesi di dottorato Problems in Computational Geometry, scritta da nel 1975. La geometria computazionale trova importanti applicazioni nella robotica, nei Sistemi Geografici Informativi (GIS), nella computer grafica, nella logistica e nel CAD/CAM, solo per citarne alcuni.