Geometria Computazionale
Docente
- Prof. Claudio Mirolo
Indirizzo e-mail
Indirizzo Pagina Web Personale
http://www.dimi.uniud.it/claudio/
Crediti
6 CFU
Finalità e obbiettivi formativi
Obiettivi del corso
Il corso si propone di esplorare l’approccio algoritmico alla soluzione di problemi di natura geometrica, applicando la conoscenza di strutture dati e di tecniche di elaborazione studiate nell’ambito della geometria computazionale. Al termine del corso lo studente avrà acquisito la capacità di valutare criticamente potenzialità, efficacia, prestazioni e robustezza degli algoritmi impiegati per la soluzioni dei problemi proposti, nonché di individuare tecniche appropriate per affrontare altri problemi di questo ambito.
Programma
Contenuti preliminari del corso
La prima parte del corso è dedicata alla definizione degli elementi 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 piana, quali: intersezioni di insiemi di segmenti, partizioni di regioni poligonali, problemi di localizzazione, vicinanza e visibilità, diagrammi di Voronoi e triangolazioni di Delaunay.
Prerequisiti
Conoscenze acquisite nei corsi di Matematica Discreta, Programmazione, Algoritmi e Strutture Dati, Programmazione Orientata agli Oggetti.
Bibliografia
M. de Berg, O. Cheong, M. van Kreveld, M. Overmars
Computational Geometry: algorithms and applications
Springer Verlag, 2008.
S. L. Devadoss, J. O’Rourke
Discrete and Computational Geometry
Princeton University Press, 2011.
A. Pascoletti: appunti del corso di geometria computazionale.
Modalità d'esame
L’esame consiste in una prova orale che verte sulla discussione di un progetto concordato con il docente su proposta dello studente. Saranno eventualmente considerati anche progetti (opportunamente dimensionati) che coinvolgono gruppi di due o tre studenti.
Orario di ricevimento
Il docente riceve su appuntamento da concordare direttamente a lezione o via e-mail.