Geometria computazionale

Da Wikipedia, l'enciclopedia libera.

La Geometria computazionale è la branca dell'Informatica che studia le strutture dati e gli algoritmi efficienti per la soluzione di problemi di natura geometrica e la loro implementazione 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 Ian Shamos 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.

Esempi di Problemi[modifica | modifica wikitesto]

Riportiamo un elenco di problemi classici risolvibili con le tecniche della Geometria computazionale

  • Inviluppo convesso (Convex Hull): dato un insieme di punti, determinare il più piccolo insieme convesso che li contenga tutti
  • Intersezione di segmenti: determinare tutte le intersezioni di un dato insieme di segmenti.
  • Diagrammi di Voronoi: dato un insieme di punti, determinare la partizione del piano in cui ogni classe di equivalenza contiene un solo punto ed è tale che tutti i suoi punti abbiano distanza minore da quel punto rispetto a tutti gli altri punti assegnati.
  • Triangolazione: Dato un poligono, determinare una sua partizione in triangoli.
  • Coppia di punti più vicina (Closest pair of points): Dato un insieme di punti, determinare la coppia di punti che ha distanza minore fra tutte.
  • Localizzazione di punti (Point location): Data una partizione del piano (o dello spazio) e un punto, determinare la classe di equivalenza che contiene quel punto.
  • Cammino minimo (Euclidean shortest path): Dati due punti del piano e un insieme di ostacoli poligonali, determinare il cammino poligonale più breve che congiunge i due punti senza intersecare gli ostacoli.
  • Range searching: Dati un insieme di punti e una regione del piano, analizzare l'insieme dei punti dati, allo scopo di contare efficientemente il numero di punti interni alla regione assegnata.
  • Intorno più vicino (Nearest neighbor): Dato un insieme di punti e un altro punto, analizzare l'insieme dato allo scopo di determinare efficientemente quale di essi ha distanza minima dal punto assegnato.
  • Triangolazioni di Delaunay
  • Programmazione lineare

Libri[modifica | modifica wikitesto]

Riportiamo un elenco dei libri di Geometria computazionale più accreditati e letti.

  • Clara I. Grima e Alberto Márquez, Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone, Kluwer Academic Publishers, 1990, ISBN 1-4020-0202-5.

Riviste[modifica | modifica wikitesto]

Riportiamo un elenco delle maggiori riviste internazionali che pubblicano articoli di ricerca di Geometria compitazionale. Si noti che all'aumentare delle riviste specificatamente dedicate a questo settore, le pubblicazioni su riviste più generiche (Informatica teorica e Computer grafica) sono sensibilmente diminuite.

Collegamenti esterni[modifica | modifica wikitesto]