INFORMAZIONI SU

Geometria Computazionale (tace a.a. 2013/2014)

Programma dell'insegnamento di Geometria Computazionale - Corso di laurea magistrale in Informatica (2013/14)

Crediti

6 CFU

Finalità

Acquisire familiarità con una serie di problemi di natura geometrica la cui soluzione richiede la conoscenza di strutture dati e di tecniche algoritmiche sorte nell'ambito della geometria computazionale. Utilizzo delle tecniche di base per lo studio di problemi più complessi. Acquisire capacità di valutazione critica dell'efficacia e della robustezza degli algoritmi e delle strutture dati impiegati per la soluzioni dei problemi proposti.

Programma

La prima parte del corso è dedicata alla definizione rigorosa degli enti geometrici di base e all’esposizione delle principali strutture per la loro gestione.
La seconda parte è dedicata alla discussione di alcuni problemi significativi della geometria computazionale nel piano (intersezioni di insiemi di segmenti, partizioni di regioni poligonali, problemi di localizzazione, vicinanza e visibilità, diagrammi di Voronoi e triangolazioni di Delaunay) con qualche escursione in ambienti di dimensione maggiore.

Bibliografia

M. de Berg, O. Cheong, M. van Kreveld, M. Overmars, Computational Geometry: algorithms and applications, terza ed., Springer Verlag, 2008.

S. L. Devadoss, J. O'Rourke, Discrete and Computational Geometry, Princeton University Press, 2011

A. Pascoletti: dispense del corso.

Modalità d'esame

Prova orale