Curso G1

Introducción a la Geometría Computacional

Dictado por: Dr. Mario López (Universidad de Denver)
Idioma: Castellano
Duración: 10hs.
Track: Computación Gráfica

Objetivos

Presentar un estudio de técnicas para el procesamiento de datos geométricos y multidimensionales.

Prerequisitos

Estructuras de datos y algoritmos básicos (ej. ordenamiento, búsqueda, stacks, colas, arboles de búsqueda, heaps), geometría analítica, conocimientos básicos de programación.

Descripción

La geometría computacional estudia soluciones eficientes para la manipulación de datos multidimensionales y geométricos. En los últimos treinta años esta disciplina ha madurado muchisimo y desarrollado técnicas con numerosas aplicaciones en graficos, robotica, bases de datos, CAD electrónico y mecánico, sistemas de información geográfica, etc.

En el presente curso se estudiaran métodos de actualidad para el diseño y análisis de algoritmos geométricos y procesamiento de datos multidimensionales. Estos métodos permiten la solución eficiente de numerosos problemas de importancia practica, como por ejemplo:

• Dada una colección de polígonos identificar rápidamente aquellos polígonos que yacen total o parcialmente dentro de una ventana gráfica
• Dado un mapa de una ciudad y las coordenadas de su automovil, reportar (a) en que zona se encuentra, y (b) donde esta la estación de gasolina mas cercana
• Dado que dos objetos no pueden ocupar el mismo espacio físico, reportar todas las intersecciones entre objetos almacenados en una base de datos arquitectonica
• Dadas las posiciones de un conjunto de vehículos identificar eficientemente los dos mas cercanos ya que son estos los que se encuentran en mayor riesgo de sufrir un accidente
• Dada una base de datos de objetos descritos por medio de feature vectors (ej. imagenes), encontrar eficientemente los cinco que mas se parecen a un objeto determinado
• Suavizar los caracteres y dibujos obtenidos por un scanner digital a manera de reducir los costos de almacenamiento y facilitar el reconocimiento de objetos

Contenido detallado

1. Problemas fundamentales
   • Ubicación de regiones
   • Detección y reporte de intersecciones
   • Problemas de proximidad
   • Problemas de visibilidad
2. Estructuras de datos:
   • Arboles multidimensionales (k-d trees, quad-trees, R-trees, binary space partition trees)
   • Archivos de malla (grid files)
   • Arboles de segmentos
   • Arboles de intervalos
   • Decomposiciones trapezoidales
3. Técnicas de diseño:
   • Barrido de espacio
   • Localización (locus)
   • Transformación geométrica
   • Dinamización
   • Aleatorización

Bibliografía

1. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry – An Introduction. Springer-Verlag. 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.
2. Herbert Edelsbrunner (1987). Algorithms in Combinatorial Geometry. Springer-Verlag. ISBN 0-89791-517-8.
3. Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars (2008). Computational Geometry (3rd revised edition ed.). Springer-Verlag. ISBN 3-540-77973-6, 1st edition (1987): ISBN 3-540-61270-X.
4. Jean-Daniel Boissonnat, Mariette Yvinec (1998). Algorithmic Geometry (Translation of a 1995 French edition ed.). Cambridge University Press. ISBN 0-521-56529-4.
5. Kurt Mehlhorn (1984). Data Structures and Efficient Algorithms 3: Multi-dimensional Searching and Computational Geometry. Springer-Verlag.
6. Ketan Mulmuley (1994). Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall. ISBN 0-13-336363-5.
7. Joseph O’Rourke (1998). Computational Geometry in C (2nd edition ed.). Cambridge University Press. ISBN 0-521-64976-5.
8. Janos Pach and Pankaj K. Agarwal (1995). Combinatorial Geometry. John Wiley and Sons. ISBN 0-471-58890-3.
9. Micha Sharir and Pankaj K. Agarwal (1995). Davenport­Schinzel Sequences and Their Geometric Applications. Cambridge University Press. ISBN 0-521-47025-0.
10. Kurt Mehlhorn and Stefan Naeher (1999). LEDA, A Platform for Combinatorial and Geometric Computing. Cambridge University Press. ISBN 0-521-56329-1.
11. Jörg-Rudiger Sack and Jorge Urrutia (1998). Handbook for Computational Geometry. North-Holland. 1st edition: ISBN 0-444-82537-1, 2nd edition: 1-584-88301-4.
12. Selim G. Akl and Kelly A. Lyons (1993). Parallel Computational Geometry. Prentice-Hall. ISBN 0-13-652017-0.
13. Hanan Samet (1990). The Design and Analysis of Spatial Data Structures. Addison-Wesley.
14. Ghosh, Subir Kumar (2007). Visibility Algorithms in the Plane. Cambridge University Press. ISBN 0521875749.