| | | corso | | | |
Matematica Computazionale: Geometria Computazionale
Codice: | AA242 | Crediti: | 6 | Semestre: | 1 | Sigla: | MCG | |
|
Settore disciplinare: | MAT/08 - Analisi Numerica |
Docente
Marco Pellegrini
Prerequisiti
Si consiglia di inviare e-mail al docente: marco.pellegrini (AT) iit.cnr.it
La prima riunione e' fissata per
Mercoledi' 28 Settembre ore 18 nel mio ufficio al CNR:
Istituto di Informatica e Telematica del C.N.R.
Area della Ricerca di Pisa. Localitą San Cataldo.
Via G. Moruzzi 1, 56100 Pisa ITALY
Ufficio: Stanza 66/3 corpo B, primo piano, entrata 18.
Obiettivi di apprendimento
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.
Programma
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.
Bibliografia
- "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.
- Per ulteriori testi vedi sito web al fondo della pagina.
Modalità di esame
Progetto e orale