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].