Università di Pisa
Laurea Specialistica in Tecnologie Informatiche
Anno Accademico 2002/2003

NW005: Matematica Computazionale: Geometria Computazionale

• Docente. Marco Pellegrini è Primo Ricercatore del CNR presso l' Istituto di Informatica e Telematica del C.N.R.
  

• Istituto di Informatica e Telematica del C.N.R.
  Area della Ricerca di Pisa. Località San Cataldo.
  Via G. Moruzzi 1, 56100 Pisa ITALY
  tel: (+39) 050 3152410
  fax: (+39) 050 3152333
  e-mail: marco.pellegrini@iit.cnr.it
  web: http://www.imc.pi.cnr.it/~pellegrini
  Ufficio: Stanza 66/3 corpo B, primo piano, entrata 18.

• 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) ed il problema della implementazione di test geometrici semplici. Un tema centrale è la ``resilienza'' ad errori di tipo numerico. In seguito si affronteranno problemi geometrici più avanzati relativi alla manipolazione dei poligoni. Al termine del corso gli studenti saranno in grado di maneggiare tecniche di base utilizzabili all'interno di più ampi progetti in Grafica e CAD/CAM.

• 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 complessita' 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.

• Libri consigliati:
  • "Introduction to Algorithms" Cormen, Leiserson and Rivest. MIT Press and McGraw-Hill, 1989 (ottava edizione). Il capitolo 35 copre gli algoritmi geometrici.

  • "Computational geometry in C", J. O'Rourke. Cambridge University Press 1994.

• Ulteriori letture:
  • "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.

  • "Computational geometry, an introduction through randomized algorithms" K. Mulmuley , Pretience Hall 1994.

  • M. de Berg, M. van Kreveld, M. Overmars e O. Schwarzkopf. ``Computational Geometry, algorithms and applications''. Springer Verlag Berlino, 1997.

• Modalità d'esame: svolgimento di un progetto.

---

Last update: 9th October 2002
[Marco's home page]