Contenido Curso de
Geometría Computacional
Cuatrimestre Agosto-Diciembre del 2006

Elaboró: Dr. Luis Gerardo de la Fraga

Objetivo: Se analizarán los principales algoritmos, desde su complejidad y realización, que se utilizan para manipular entidades geométricas en dos y tres dimensiones.

10/11/2006 El código para calcular la cubierta convexa por el
algoritmo de Andrew Andrew.tar.gz

07/11/2006 El código para realizar el ordenamiento circular y la
cubierta convexa por el algoritmo de Graham: Graham.tar.gz

24/10/2006 El código para realizar una triangulación: tri.tar.gz

Contenido:

1/3 Parte. Dr. Guillermo Morales Luna. Geometría proyectiva

2/3 Partes. Dr. Luis Gerardo de la Fraga

1. Inducción matemática.
2. Triangulación de polígonos
   1. El problema de la galería de arte
   2. Cálculo del área de un polígono
   3. Algoritmo de triángulación de complejidad O(n^2)
   4. Partición de un polígono es sus piezas monótonas-y
   5. Algoritmo de triangulación de un polígono monótono-y de complejidad O(n log n)
3. La cubierta convexa
1. Definiciones
2. Algoritmo de Graham
3. Algoritmo de Andrew
4. Algoritmo QuickHull
5. Análisis de complejidad
4. Cálculo de la cubierta convexa en tres dimensiones
5. Diagramas de Voronoi
6. Triangulación de Delaunay
7. Búsqueda e intersección
1. Intersección de línea contra línea
2. Intersección de línea contra triángulo
3. Intersección de linea contra cuadrilátero
4. Intersección de linea contra cajas

Bibliografía:

1. Computational Geometry an introduction. F.P. Preparata. 1985. Springer
2. Computational geometry, algorithms and applications. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Springer.
3. Computational Geometry in C. J. O'Rourke, Cambridge Tracts in Theoretical Computer Science.
4. Real Time Collision Detection. C. Ericson. 2005. Morgan Kaufmann
5. Collision detection in interative 3D enviroments. G. van den Bergen 2004. Morgan Kaufmann