Matematica Computazionale: Geometria Computazionale

Marco Pellegrini  

(AS1) Algoritmi e Strutture dati 1

Il corso si propone di famigliarizzare gli studenti a tecniche algoritmiche efficienti per la risoluzione di problemi geometrici sul piano.

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. Inizialmente affrontiamo il problema della rappresentazione degli oggetti geometrici all'interno di linguaggi di programmazione (per esempio il C) per passare poi alla implementazione di test geometrici via via più complessi.

This course introduces efficient algorithmic techniques for solving geometric problems in planar geometry. Emphasis will be placed on efficient algorithms for set of points, segments and polygons.

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

- "Introduction to Algorithms" Cormen, Leiserson and Rivest. MIT Press and McGraw-Hill, 1989 (ottava edizione). Il capitolo 35 copre algoritmi geometrici. - "Computational geometry in C", J. ÒRourke. Cambridge University Press 1994. - "Computational geometry: an introduction", F.P. Preparata e M.I. Shamos, Springer-Verlag, 1985. - "Algorithms in Combinatorial geometry" H. Edelsbrunner, EATCS Monograph on Theoretical Computer Science, Springer Verlag 1987. - M. de Berg, M. van Kreveld, M. Overmars e O. Schwarzkopf. ``Computational Geometry, algorithms and applications''. Springer Verlag Berlino, 1997.

Scritto e orale