Appunti di Geometria Computazionale

Andrea Fusiello - 2008

La Geometria Computazionale studia algoritmi che risolvono problemi geometrici Ha molte applicazioni in Informatica, Ingegneria e Matematica, tra le quali citiamo grafica, robotica, progetto di circuiti VLSI, CAD, ricerca operativa e statistica Queste aree applicative forniscono problemi di natura geometrica per i quali è necessario sviluppare algoritmi efficienti Dal punto di vista teorico lo studio della complessità degli algoritmi geometrici è interessante in quanto mette in luce la inerente difficoltà dei problemi I problemi tipici sono: calcolo del guscio convesso, problemi di prossimità, ricerca geometrica, intersezioni Pur mantenendo sempre un taglio applicativo, con lo scopo di motivare la rilevanza dei problemi affrontati, non verrà mai trascurato l'aspetto formale sia nello sviluppo degli strumenti geometrici che nell'analisi della complessità computazionale

• Appunti.pdf

Argomenti

• Preliminari
• Geometrici
• Algoritmici
• Operazioni di base
• Orientamento di una terna di punti
• Triangolazione del poligono
• Poligoni
• Triangolazione di poligoni semplici
• Algoritmo del taglio degli orecchi
• Guscio convesso
• Graham’s scan
• Algoritmo incrementale
• Jarvis’s march
• QuickHull
• MergeHull (cenni)
• Guscio convesso in D (cenni)
• Applicazioni
• Intersezioni
• Intersezione di segmenti
• Test di intersezione
• Algoritmo plane sweep
• Intersezione di poligoni
• Algoritmo plane sweep
• Metodo delle strisce
• Algoritmo plane sweep per poligoni convessi
• Intersezione di semipiani
• Algoritmo “divide-et-impera”
• Intersezione di semispazi in 3D (cenni)
• Suddivisioni piane
• Grafi piani
• Suddivisione piana
• DCEL
• Triangolazione di punti
• Algoritmo incrementale
• Disposizione di rette
• Algoritmo incrementale
• Dualitàa punto-retta
• Ricerca geometrica
• Localizzazione di un punto in un poligono
• Metodo di Jordan
• Metodo dei semipiani
• Metodo delle fette
• Localizzazione di un punto in un poliedro (cenni)
• Localizzazione di un punto in una suddivisione piana
• Metodo delle strisce
• Range search
• Point Quadtree
• k-d Tree
• Prossimità
• Closest pair: Algoritmo di Shamos
• Diagramma di Voronoi
• Algoritmo divide-et-impera (cenni)
• Algoritmo di Fortune
• Applicazioni
• Triangolazione di Delaunay
• Flip algorithm
• Proprietà del max-min angolo
• Algoritmo incrementale
• Sollevamento e guscio convesso
• Problemi collegati
• Minimo albero di ricoprimento
• Applicazioni

Tutto il materiale non coperto da altre forme di copyright viene pubblicato con Licenza Creative Commons Attribuzione-NonCommerciale-Condividi allo stesso modo.

Unique hits: 759