Discussione di problemi significativi della geometria computazionale piana, in particolare: convex hull, intersezioni di insiemi di segmenti, partizioni di regioni poligonali, problemi di localizzazione, vicinanza e visibilità, diagrammi di Voronoi e triangolazioni di Delaunay.

1. Cenni alle problematiche legate all’elaborazione numerica nella geometria computazionale.

– Informazioni relative alle strutture geometriche: topologia e misure spaziali;

– Problemi legati all’aritmetica floating-point;

– Elaborazione algoritmica: decisioni e costruzione di nuovi oggetti.

2. Costruzione del convex hull di un insieme di punti nel piano: proprietà geometriche, casi degeneri, analisi dei costi.

– “Graham’s scan”: ordinamento lessicografico, ottimalità e robustezza;

– Approccio divide-et-impera (Preparata & Hong).

– Approccio randomizzato (Devillers): gestione dei “conflitti”, backward analysis.

3. Cenni alla generalizzazione in 3D.

– Schema divide-et-impera (Preparata & Hong);

– Schema randomizzato (Devillers).

– Altri risultati relativi al convex hull: analisi “output-sensitive”.

4. Intersezioni di un insieme di segmenti nel piano: tecnica di plane sweep.

– Concetto di “sweep line” ed eventi;

– Ordinamento lessicografico degli eventi;

– Ordinamento dei segmenti intercettati dalla sweep line: struttura BST e relativi eventi;

– Test di intersezione di Sharir & Hoey;

– Algoritmo di Bentley & Ottmann: coda con priorità e BST, analisi della complessità;

– Altri algoritmi: Chazelle & Edelsbrunner, randomizzato (Mulmuley).

5. Struttura DCEL: Doubly-Connected Edge List.

– Sovrapposizione di suddivisioni piane rappresentate da DCEL.

6. Problemi affrontabili attraverso triangolazioni.

– “Guarding art galleries”: triangolazione e tricolorazione;

– Triangolazione di un poligono semplice: esistenza di una triangolazione;

– Tricolorazione dei vertici di un poligono semplice: esistenza e ottimalità;

– Algoritmo per la triangolazione: suddivisione in componenti monotone e vertici SPLIT/MERGE;

– Tecnica di plane sweep per la triangolazione: invarianti del processo di plane sweep;

– Algoritmo di Lee & Preparata;

– Algoritmo di Chazelle per un poligono semplice.

7. Mappe trapezoidali.

– Point location e bounding box;

– Classificazione e numerosità delle regioni di una mappa trapezoidale:

– Algoritmo randomizzato incrementale: DAG e tipologie di nodi;

– Stima dei costi di point location: backward analysis.

– Trattamento di casi degeneri.

8. Point location in suddivisioni piane monotone.

– Ordinamento lineare delle regioni e famiglia di separatori;

– Algoritmo di Lee & Preparata;

– Algoritmo di Edelsbrunner, Guibas & Stolfi: costruzione del layered DAG e stima dei costi di preelaborazione.

9. Diagrammi di Voronoi.

– Caratterizzazione e complessità strutturale;

– Costruzione di un diagramma di Voronoi: lower bound;

– Algoritmo di Fortune: sweep line e “beach line”, caratterizzazione degli eventi, analisi dei costi computazionali;

– Algoritmo “divide et impera” di Shamos & D. Hoey: tecnica.

10. Triangolazione di un insieme di punti.

– Complessita’ di una triangolazione;

– Triangolazioni di Delaunay: grafi e triangolazioni di Delaunay;

– Algoritmo incrementale randomizzato e stima dei costi di point location.