Matematica Computazionale: Geometria Computazionale

Marco Pellegrini  

Lo scopo del corso di geometria computazionale è di introdurre gli studenti alle tecniche algoritmiche per la risoluzione di problemi di natura geometrica. L'enfasi sarà su problemi di tipo planare aventi come oggetto insiemi di punti e poligoni.

Unità 1: Introduzione, e panoramica sulla geometria computazionale.
Unità 2: Test geometrici elementari. Intersezione di segmenti
Unità 3. Rappresentazione di punti, poligoni. Area del triangolo, area di poligoni convessi e non-convessi. Virate destre e sinistre.
Unità 4 e 5. Tecnica dello ``Sweeping line''. Individuazione di intersezioni in insiemi di segmenti. Algoritmo di Bentley e Ottman.
Unità 6 e 7. Inviluppi convessi ``Convex Hull'': Definizione e applicazioni. Algoritmi efficienti: Algoritmo di Graham e Algoritmo di Jarvish.
Unità 8. Triangolazione di un poligono semplice. Un metodo a complessità cubica ed un metodo a complessità quadratica.
Unità 9. Problemi di ricerca su poligoni. Punto-in-poligono-convesso. Punto-in-poligono-non-convesso.
Unità 10. Coppia di punti più vicini. Algoritmo di Shamos-Hoey.

"Introduction to Algorithms" Cormen, Leiserson and Rivest. MIT Press and McGraw-Hill, 1989 (ottava edizione). Il capitolo 35 tratta gli algoritmi geometrici. "Computational geometry in C", J. ÒRourke. Cambridge University Press 1994.

Scritto e orale