Università di Pisa
Dottorato in Informatica
Anno 2004
Metodi Probabilistici in 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.
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 introdurre lo studente ad alcune
tecniche per il disegno di algoritmi probabilistici efficienti
sviluppati nell'ultimo decennio ed alla loro applicazione
principalmente nel campo della geometria computazionale.
Si studieranno problemi applicativi di tipo planare che
coinvolgono poligoni e insiemi di poligoni (mappe planari,
diagrammi di Voronoi) all'interno di una teoria più generale di
natura combinatorica (Spazi di configrazioni, Random sampling,
epsilon-nets). Si giungerà quindi a dimostrare bounds
asintotici sul tempo medio di soluzione di svariati problemi e
``tail estimates'' sulla deviazione di tali tempi dalla media.
- Le lezioni si svolgono al martedì e giovedì dalle
ore 16 alle 18, presso Aula Seminari Ovest del Dipartimento di Informatica.
Eventuali variazioni saranno comunicate sulla mailing list del
corso. Per essere inseriti nella mailing list basta inviare una
richiesta per e-mail all'istruttore.
-
Dispense del corso.
Avverteza.
Le dispense del corso non sono state soggette al normale processo
di revisione riservato al materiale per la pubblicazione. Le
dispense possono essere distribuite fuori dalla classe solo col
permesso dell'istruttore.
Disclaimer.
These notes have not been subjected to the usual scrutiny
reserved for formal publications. They may be distributed outside
this class only with the permission of the Instructor.
15/1/04 Lezione 1. Randomized quick-sort Note
Lucidi
20/1/04 Lezione 2. Skip lists Note
Lucidi
22/1/04 Lezione 3. Trapezoidal decompositions Note
Lucidi
27/1/04 Lezione 4. Intersection of halfspaces Note
Lucidi
03/2/04 Lezione 5. Voronoi Diagrams and Delaunay Triangulations Note
05/2/04 Lezione 6. Chernoff Bounds and Configuration Spaces Note
Lucidi
10/2/04 Lezione 7. Random sampling Note
Lucidi
12/2/04 Lezione 8. Average conflict size Note
Lucidi
17/2/04 Lezione 9. Epsilon-nets and VC-dimension Note
19/2/04 Lezione 10. Linear Programming Note
Lucidi
-
Articoli proposti per i Seminari degli Studenti.
(1) L. Engebretsen, P. Indyk, and R. O'Donnell.
Derandomized dimensionality reduction with applications.
In Proc. 13th Annual ACM-SIAM Symposium on Discrete Algorithms,
2002 pp. 705-712. Questo articolo e' interessante per
l'applicazione del metodo delle probabilita' condizionate.
(2) Piotr Indyk, Rajeev Motwani
Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality.
STOC 1998 pp. 604-613. In questo articolo ci interessa soprattutto
la tecnica del "locality sensitive hashing".
Riservato a Daniela De Col.
(3) Jon M. Kleinberg
Two Algorithms for Nearest-Neighbor Search in High Dimensions.
STOC 1997 pp. 599-608. Un'interessante applicazione delle
"epsilon-approximations".
(4) B. Gartner and E. Welzl
A simple sampling lemma: Analysis and applications in geometric optimization,
Discr. Comput. Geometry, 25(4): 569-590 (2001). Un'analisi
completa di un semplice lemma sul sampling con varie applicazioni.
Riservato ad Alessandro Passaro.
(5) Michel X. Goemans, David P. Williamson
A new 3/4-Approximation Algorithm for MAX SAT.
SIAM J. Discrete Math. 7(4): 656-666 (1994).
Here quite straightforward probabilistic consideration yield a good
approximation algorithms for a classic NP-complete problem.
Riservato a Diego Puppin.
(6) Raimund Seidel.
On the All-Pairs-Shortest-Path Problem.
STOC 1992. pp 745-749. Here quite straightforward probabilistic
considerations yield a good algorithms for a classic graph problem.
Reserved for Francesca Leonetti.
(7) Nancy M. Amato, Michael T. Goodrich, Edgar A. Ramos
Linear-Time Triangulation of a Simple Polygon Made Easier Via Randomization
Symposium on Computational Geometry 2000, pp 201-212.
A quite big step towards a simple algorithm for triangulating a
siple polygon in linear time.
Riservato a Rosana Matuk.
(8) A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, E. Ramos
Randomized External-Memory Algorithms for Some Geometric Problems
Symposium on Computational Geometry 1998, pp. 259-268.
Costruzioni incrementali randomizzate nel modello di costo con
memeoria esterna.
(9) S. Har-Peled.
Constructing planar cuttings in theory and practice.
SIAM J. Comput. 2000 vol 29 pp 2016--2039. Optimal cuttings can be
constructed efficiently.
Reserved for Quinghua Zhan.
(10) David R. Karger, Philip N. Klein, Robert E. Tarjan.
A Randomized Linear-Time Algorithm to Find Minimum Spanning Trees.
Journal of the ACM, vol 42, pp. 321--328, 1995. To be read
together with the simplified analysis in T. Chan,
Backwards analysis of the Karger-Klein-Tarjan algorithm for minimum spanning
trees. Information Processing Letters, 67:303-304, 1998.
Reserved for Massimo Bartoletti.
(11) Micha Sharir.
The Clarkson-Shor technique revisited and extended.
Proceedings of the seventeenth annual symposium on Computational
Geometry, 2001. A nice and elegant proof of basic theorems on the
size of conflict lists. Reserved for Giacomo Tommei.
Last update: 19th January 2004
[Marco's home page]