Rss Feed
Tweeter button
Facebook button
Myspace button
Linkedin button
Delicious button
Digg button

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.