Geometria computazionale - Computational Geometry
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.
********************************************************************************************
Aims
The course explores the algorithmic approach to problems of geometric nature, whose solutions require data structures and processing techniques specific to computational geometry. The student is expected to develop the ability to critically assess potentials, efficiency and robustness of the considered algorithms, as well as to figure out appropriate solutions to new related problems.
Syllabus
The first part of the course is about the definition of basic geometric objects and data structures to manipulate such objects.
In the second part some important problems of planar geometry are discussed, such as: segment intersections, polygonal partitioning, point location, proximity and visibility problems, Voronoi diagrams and Delaunay triangulations.
Prerequisites
Concepts and techniques introduced in the courses of Discrete Mathematics, Intorductory Programming, Algorithms and Data Structures, Object-Oriented Programming.
References
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.
Exams
Oral discussion of a project proposed by the student (or by a small group of students).