Università degli Studi L'Aquila Dipartimento di Matematica Pura ed Applicata Via Vetoio, Località Coppito, 67010 L'AQUILA PROGRAMMA DEL CORSO Algoritmi e Strutture Dati II: Dati Geometrici e Multidimensionali A.A. 1998/99 Docente: Guido Proietti

 
 

• PARTE PRIMA: Elementi di Geometria Computazionale

1. Elementi introduttivi. Proprietà dei segmenti. Prodotti incrociati. Determinazione della svolta a sinistra tra segmenti consecutivi [Rif. 1, pp. 835-840].
2. Verifica dell'intersezione tra due segmenti. Verifica dell'intersezione di una coppia qualsiasi di segmenti. Algoritmo di rastrellamento (plane sweep) [Rif. 1, pp. 840-846].
3. Calcolo dell'inviluppo convesso di un insieme di punti (convex hull). Algoritmo di Graham. Algoritmo di Jarvis [Rif. 1, pp. 846-854].
4. Ricerca della coppia di punti più vicina. Algoritmo divide-et-impera [Rif. 1, pp. 854-858].
5. Determinazione dell'inclusione di un punto in poligoni convessi e a stella [Rif. 2, pp. 36-45].
6. Range query su un insieme di punti. Metodo della griglia. Report query risolta con l'uso del 2-D-tree [Rif. 2, pp. 70-78].
7. Il diagramma di Voronoi e la triangolazione di Delaunay (cenni) [Rif. 2, pp. 185-210].
8. Calcolo del minimo albero ricoprente Euclideo di un insieme di punti utilizzando il diagramma di Voronoi e la triangolazione di Delaunay. [Rif. 2, Par. 6.1]
9. Intersezione di rettangoli. L'interval tree . Intersection query [Rif. 2, Par. 8.8.1].
 
 
• PARTE SECONDA: Algoritmi e strutture dati per dati spaziali

1. Elementi introduttivi. Nozione di dato spaziale opposta alla nozione di dato geometrico. Interrogazioni spaziali [Rif. 3, pp. 4-12].
2. La famiglia dei quadtree. Il quadtree in memoria principale per immagini binarie. Il quadtree in memoria secondaria: la DF-expression ed il linear quadtree. La exist e la select query sul linear quadtree per immagini binarie [Rif. 4].
3. Immagini non binarie con caratteristiche non sovrapposte: l'HL-tree. La exist e la select query sull'HL-tree [Rif. 5].
4. Immagini non binarie con caratteristiche sovrapposte: il MOF-tree. La exist e la select query sul MOF-tree. Complessità spaziale del MOF-tree opposta a quella dei linear quadtree multipli nel modello probabilistico basato sulla generazione di alberi random [Rif. 6].
5. La piramide. La exist e la select query sulla piramide. Algoritmo efficiente di decomposizione di una finestra di query nei suoi blocchi massimali. Codifica di omogeneità-eterogeneità basata su 2 bit [Rif. 7].
6. L'R-tree. Algoritmi di inserimento tramite split lineare e quadratico. Algoritmo di cancellazione [Rif. 8].
7. Varianti dell'R-tree: l'R+-tree, l'R*-tree (cenni), l'Hilbert R-tree (cenni), il P-tree (cenni) [Rif. 9].
8. Modelli di previsione del comportamento degli R-tree in risposta a range query. Modello uniforme. Modello basato sui frattali [Rif. 10].
 
 
• Bibliografia

1. T.H. Cormen, C.E. Leiserson e R.L. Rivest, Introduzione agli Algoritmi, Volume 3, Ed. Jackson Libri.
2. F. Preparata e Shamos, Computational Geometry: an Introduction, Ed. Springer-Verlag.
3. V. Gaede e O. Günther, Multidimensional Access Methods, Computing Surveys 30(2): 170-231 (1998).
4. E. Nardelli e G. Proietti, Efficient secondary memory processing of window queries on spatial data, Information Sciences, 80: 1-17 (1994).
5. E. Nardelli e G. Proietti:, Time and Space Efficient Secondary Memory Representation of Quadtrees, Information Systems, 22(1): 25-37 (1997).
6. Y. Manolopoulos, E. Nardelli, A. Papadopoulos e G. Proietti, MOF-Tree: A Spatial Access Method to Manipulate Multiple Overlapping Features, Information Systems, 22(8): 465-481 (1997).
7. G. Proietti, An optimal algorithm for decomposing a window into maximal quadtree blocks, Acta Informatica, in stampa.
8. A. Guttman, R-Trees: A Dynamic Index Structure for Spatial Searching, SIGMOD Conference, 1984: 47-57.
9. T.K. Sellis, N. Roussopoulos e C. Faloutsos, The R+-Tree: A Dynamic Index for Multi-Dimensional Objects, VLDB Conference, 1987: 507-518.
10. C. Faloutsos e I. Kamel, Beyond Uniformity and Independence: Analysis of R-trees Using the Concept of Fractal Dimension, PODS Conference, 1994: 4-13.