Home Teaching - Computational Geometry September 02, 2010   

Geometría Computacional

Objetivo general
  • Este curso tiene como objetivo que los estudiantes adquieran los conocimientos y competencias en el área de Geometría Computacional (GC) necesarios para diseñar e implementar algoritmos eficientes para resolver problemas en geometría, tales como: Cubiertas convexas (convex hulls), intersecciones geométricas, diagramas de Voronoi, triangulaciones de Delaunay, estructuras de datos geométricas, etc.
Contenido temático
  • Introducción a la GC
  • Cubiertas convexas
  • Intersección de segmentos de línea
  • Triangulación de polígonos
  • Programación lineal
  • Búsqueda de rango ortogonal
  • Localización de puntos en el plano
  • Diagramas de Voronoi
  • Arreglos de líneas y dualidad
  • Triangulación de Delaunay
Lineamientos de evaluación
  • Tareas y trabajos de investigación, 25%
  • 3 examenes rápidos, 20%
  • Examen parcial, 25%
  • Proyecto final, 30%
Bibliografía
  • Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition (April 16, 2008), ISBN-10: 3540779736.
  • Joseph O'Rourke. Computational Geometry in C. Cambridge University Press; 2000 edition (February 15, 2001), ISBN-10: 0521649765.
Material de clase
Sesión Fecha Tema Material
1 12/01/10 Presentación del curso
Introducción a la GC
2 14/01/10 Conceptos básicos de Geometría
Tarea 1: Preparar un reporte en Latex y PSTricks con un ejemplo numérico y gráfico (si es posible) para los siguientes conceptos:
  1. Cuatro operaciones legales de la geometría afín (diapositiva 6)
  2. Combinación afín de 2 puntos y 2 escalares (diapositiva 8)
  3. Combinación afín de 3 puntos y 3 escalares (diapositiva 11)
  4. Producto punto (diapositiva 13)
  5. Longitud, normalización y distancia entre puntos (diapositiva 14)
  6. Orientación de 3 puntos y área del tríangulo (diapositiva 19)
  7. Ángulo descrito por 2 vectores (diapositivas 24 y 25)
Fecha de entrega: 21 de enero del 2010 antes de las 8h00 		.
3 19/01/10 Cubiertas convexas (slowConvexHull y Graham)
Tarea 2: Implementación de los algoritmos para cubiertas convexas vistos en clase, con una interfaz gráfica que permita visualizar los puntos y la cubierta resultante (ver diapositiva 30 de la sesión 3).

Fecha de entrega: 28 de enero del 2010 antes de las 8h00 		.
4 21/01/10 Cubiertas convexas II (Divide y Vencerás)
5 26/01/10 Cubiertas convexas III (QuickHull y Caminata de Jarvis)
Tarea 3: Implementación de los algoritmos para cubiertas convexas vistos en clase (ver diapositivas 24 y 25 de la sesión 5).

Fecha de entrega: Jueves 4 de febrero del 2010 antes de las 8h00 		.
6 28/01/10 Revisión Tarea 2 .
7 02/02/10 Cubiertas convexas IV (Algoritmo de Chan)
8 04/02/10 Revisión Tarea 3 .
9 09/02/10 Quiz 01 .
10 11/02/10 Politopos y cubiertas convexas en 3 o más dimensiones
Tarea 4: Implemente el algoritmo de Chan para el cálculo de cubiertas convexas (ver diapositiva 37 de la sesión 10).

Fecha de entrega: 18 de febrero del 2010 antes de las 8h00 		.
Tarea 5: En equipos de dos personas realizar una investigación sobre las estructuras de datos conocidas como AVL Tree, Segment Tree, Winged-edge, Quad-edge, y Half-edge para preparar una exposición de 20 minutos (usando Latex y beamer).

Fecha de entrega: 23 de febrero del 2010 antes de las 8h00 		.
11 16/02/10 Politopos y cubiertas convexas en 3 o más dimensiones (continuación)
12 18/02/10 Intersección de segmentos de línea
13 23/02/10 Exposiciones por parte de los alumnos sobre estructuras de datos geométricas: AVL Tree, Segment Tree, Winged-edge, Quad-edge, y Half-edge .
AVL Tree
Segment Tree
Winged-edge
Quad-edge
Half-edge
14 25/02/10 Algoritmo de barrido del plano (plane sweep)
Tarea 6: Implementación del algoritmo de barrido del plano (plane sweep) para encontrar los puntos de intersección de un conjunto de segmentos de línea. Prepare además un reporte (en Latex) donde se expliquen los detalles de la implementación realizada, así como los resultados del conjunto de experimentos efectuados para probar el desempeño de su algoritmo.

Fecha de entrega: 11 de marzo del 2010 antes de las 8h00 		.
15 y 16 02/03/10 y 04/03/10 Triangulación de polígonos (Presentación actualizada)
17 09/03/10 Examen parcial .
18 11/03/10 Solución del Examen parcial .
19 16/03/10 Intersección de semiplanos
Tarea 7: Implementación del algoritmo de triangulación de polígonos visto en clase (2 y 4 de marzo). Prepare también un reporte (en Latex) donde se presenten los detalles de la implementación realizada, así como los resultados del conjunto de experimentos efectuados para probar el desempeño de su algoritmo.

Fecha de entrega: 30 de marzo del 2010 antes de las 8h00 		.
Tarea 8: Implemente el algoritmo para resolver el problema de intersección de semiplanos visto en clase. Prepare además un reporte (en Latex) donde se expliquen los detalles de la implementación realizada, así como los resultados de sus experimentos para probar el desempeño del algoritmo.

Fecha de entrega: 20 de abril del 2010 antes de las 8h00 		.
20 18/03/10 Programación lineal (Suspensión por problemas en la red) .
21 23/03/10 Programación lineal
Algunos ejemplos de PL:
  1. http://www.omerique.net/twiki/pub/Calcumat/PepeMellado/Problemadeprogramacinlineal.pdf
  2. http://actividadesinfor.webcindario.com/proli.htm
 .
22 25/03/10 Localización de puntos en el plano
23 30/03/10 Suspensión oficial de labores .
24 01/04/10 Suspensión oficial de labores .
25 06/04/10 Diagramas de Voronoi
26 08/04/10 Triangulaciones de Delaunay
27 13/04/10 Triangulación de Delaunay (construcción incremental)
28 20/04/10 Revisión de avance del proyecto final .
29 y 30 22/04/10 y 29/04/10 Entrega del proyecto final .



® 2008 Eduardo Rodriguez-Tello