Geometria computazionale

La geometria computazionale è la branca della geometria che studia gli algoritmi efficienti per la soluzione di problemi di natura geometrica, e la loro implementazione informatica al calcolatore.

Per "algoritmo efficiente" si intende un algoritmo che ha una bassa complessità computazionale, cioè che impegna la minore quantità di risorse possibili in termini di tempo impiegato e di spazio di memoria occupata in funzione della dimensione del problema.

Per "algoritmo esatto" si intende un algoritmo che, mediante l'uso di apposite tecniche, eviti le operazioni computazionalmente a rischio di errori di arrotondamento (in special modo le divisioni e le funzioni trigonometriche).

Sebbene la Geometria computazionale sia una disciplina relativamente recente, essa utilizza risultati di molti altri campi della Matematica, quali l'algebra lineare, la topologia e la geometria combinatoria (in special modo la teoria dei grafi).

Il nome Geometria computazionale è stato coniato da Marvin Minsky nel suo libro Perceptrons, ma è stato usato per la prima volta col significato corrente nella tesi di dottorato Problems in Computational Geometry, scritta da Ian Shamos nel 1975.

La geometria computazionale trova importanti applicazioni nella robotica, nei Sistemi Geografici Informativi (GIS), nella computer grafica, nella logistica e nel CAD/CAM, solo per citarne alcuni.

Esempi di Problemi

Riportiamo un elenco di problemi classici risolvibili con le tecniche della geometria computazionale:

• Inviluppo convesso (Convex Hull): dato un insieme di punti, determinare il più piccolo insieme convesso che li contenga tutti.
• Intersezione di segmenti: determinare tutte le intersezioni di un dato insieme di segmenti.
• Diagrammi di Voronoi: dato un insieme di punti, determinare la partizione del piano in cui ogni classe di equivalenza contiene un solo punto, ed è tale che tutti i suoi punti abbiano distanza minore da quel punto rispetto a tutti gli altri punti assegnati.
• Triangolazione: dato un poligono, determinare una sua partizione in triangoli.
• Coppia di punti più vicina (Closest pair of points): dato un insieme di punti, determinare la coppia di punti che ha distanza minore fra tutte.
• Localizzazione di punti (Point location): data una partizione del piano (o dello spazio) e un punto, determinare la classe di equivalenza che contiene quel punto.
• Cammino minimo (Euclidean shortest path): dati due punti del piano e un insieme di ostacoli poligonali, determinare il cammino poligonale più breve che congiunge i due punti senza intersecare gli ostacoli.
• Range searching: dati un insieme di punti e una regione del piano, analizzare l'insieme dei punti dati, allo scopo di contare efficientemente il numero di punti interni alla regione assegnata.
• Intorno più vicino (Nearest neighbor): dato un insieme di punti e un altro punto, analizzare l'insieme dato allo scopo di determinare efficientemente quale di essi ha distanza minima dal punto assegnato.
• Triangolazioni di Delaunay
• Programmazione lineare

Libri

Riportiamo un elenco dei libri di geometria computazionale più accreditati e letti:

• Franco P. Preparata e Michael Ian Shamos, Computational Geometry - An Introduction, Springer-Verlag, 1985, 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3; Russian translation, 1989: ISBN 5-03-001041-6.

• Herbert Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987, ISBN 0-89791-517-8.

• Mark de Berg, Otfried Cheong, Marc van Kreveld, e Mark Overmars, Computational Geometry, 3rd revised edition, Springer-Verlag, 2008, ISBN 3-540-77973-6, , 1st edition (1987):.

• Jean-Daniel Boissonnat, Mariette Yvinec, Algorithmic Geometry, Translation of a 1995 French edition, Cambridge University Press, 1998, ISBN 0-521-56529-4.

• Kurt Mehlhorn, Data Structures and Efficient Algorithms 3: Multi-dimensional Searching and Computational Geometry, Springer-Verlag, 1984.

• Ketan Mulmuley, Computational Geometry: An Introduction Through Randomized Algorithms, Prentice-Hall, 1994, ISBN 0-13-336363-5.

• Joseph O'Rourke, Computational Geometry in C, 2nd edition, Cambridge University Press, 1998, ISBN 0-521-64976-5.

• Janos Pach e Pankaj K. Agarwal, Combinatorial Geometry, John Wiley and Sons, 1995, ISBN 0-471-58890-3.

• Micha Sharir e Pankaj K. Agarwal, Davenport–Schinzel Sequences and Their Geometric Applications, Cambridge University Press, 1995, ISBN 0-521-47025-0.

• Kurt Mehlhorn e Stefan Naeher, LEDA, A Platform for Combinatorial and Geometric Computing, Cambridge University Press, 1999, ISBN 0-521-56329-1.

• Jörg-Rüdiger Sack e Jorge Urrutia, Handbook for Computational Geometry, North-Holland, 1998, 1st edition: ISBN 0-444-82537-1, 2nd edition: 1-584-88301-4.

• Selim G. Akl e Kelly A. Lyons, Parallel Computational Geometry, Prentice-Hall, 1993, ISBN 0-13-652017-0.

• Joseph O'Rourke, Art Gallery Theorems and Algorithms, Oxford University Press, 1987.

• Hanan Samet, The Design and Analysis of Spatial Data Structures, Addison-Wesley, 1990.

• Clara I. Grima e Alberto Márquez, Computational Geometry on Surfaces: Performing Computational Geometry on the Cylinder, the Sphere, the Torus, and the Cone, Kluwer Academic Publishers, 1990, ISBN 1-4020-0202-5.

• Subir Kumar Ghosh, Visibility Algorithms in the Plane, Cambridge University Press, 2007, ISBN 0-521-87574-9.

• Giri Narasimhan, Michiel Smid, Geometric Spanner Networks, Cambridge University Press, 2007, ISBN 0-521-81513-4.

• Jacob E.Goodman e Joseph O'Rourke (editors), Handbook for Computational Geometry, North-Holland, 1997, 2004, 1st edition: ISBN 0-8493-8524-5, 2nd edition: ISBN 1-584-88301-4.

• J. R. Sack e J. Urrutia (eds.), Handbook of Computational Geometry, North Holland, 2000, ISBN 0-444-82537-1.

Riviste

Riportiamo un elenco delle maggiori riviste internazionali che pubblicano articoli di ricerca di Geometria computazionale. Si noti che all'aumentare delle riviste specificatamente dedicate a questo settore, le pubblicazioni su riviste più generiche (Informatica teorica e Computer grafica) sono sensibilmente diminuite.

• ACM Computing Surveys
• ACM Transactions on Graphics
• Acta Informatica
• Advances in Geometry
• International Journal oF Differential Geometry(www.ijournaldg.cc.cc)
• Algorithmica
• Ars Combinatoria
• Computational Geometry: Theory and Applications
• Communications of the ACM
• Computer Aided Geometric Design
• Computer Graphics and Applications
• Computer Graphics World
• Discrete & Computational Geometry
• Geombinatorics
• Geometriae Dedicata
• IEEE Transactions on Graphics
• IEEE Transactions on Computers
• IEEE Transactions on Pattern Analysis and Machine Intelligence
• Information Processing Letters
• International Journal of Computational Geometry and Applications
• Journal of Combinatorial Theory, series B
• Journal of the ACM
• Journal of Algorithms
• Journal of Computer and System Sciences
• Management Science
• Pattern Recognition
• Pattern Recognition Letters
• SIAM Journal on Computing
• SIGACT News; featured the "Computational Geometry Column" by Joseph O'Rourke
• Theoretical Computer Science
• The Visual Computer

Altri progetti

• Wikimedia Commons contiene immagini o altri file sulla geometria computazionale

Collegamenti esterni

• (EN) Opere riguardanti Computational geometry, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Computational Geometry, su MathWorld, Wolfram Research.
• (EN) computational geometry, in Free On-line Dictionary of Computing, Denis Howe. Disponibile con licenza GFDL
• Computational Geometry, su computational-geometry.org.
• Computational Geometry Pages, su compgeom.cs.uiuc.edu. URL consultato il 2 marzo 2010 (archiviato dall'url originale il 6 novembre 2011).
• Geometry In Action, su ics.uci.edu.
• "Strategic Directions in Computational Geometry — Working Group Report" (1996), su cs.brown.edu.

Portale Informatica

Portale Matematica