Home Teaching - Computational Geometry December 10, 2023   

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, 30%
  • Exámenes, 30%
  • Proyecto final, 40%
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 08/01/13 Presentación del curso
Introducción a la GC
2 15/01/13 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: 22 de enero del 2013 antes de las 12h00 		.
3 18/01/13 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: 29 de enero del 2013 antes de las 12h00 		.
4,5 22/01/13 y 25/01/13 Cubiertas convexas II (Divide y Vencerás, QuickHull y Caminata de Jarvis)
Tarea 3: Implementación de los algoritmos para cubiertas convexas vistos en clase (ver diapositivas 40 y 41 de la sesión 4).

Fecha de entrega: 5 de febrero del 2013 antes de las 12h00 		.
6 29/01/13 Cubiertas convexas III (Algoritmo de Chan)
Revisión Tarea 2 .
Tarea 4: Implemente el algoritmo de Chan para el cálculo de cubiertas convexas (ver diapositiva 30 de la sesión 6).

Fecha de entrega: 12 de febrero del 2013 antes de las 12h00 		.
7 01/02/13 Politopos y cubiertas convexas en 3 o más dimensiones
8 08/02/13 Politopos y cubiertas convexas en 3 o más dimensiones (continuación)
9 12/02/13 Estructuras de datos geométricas
Tarea 5: Implemente un algoritmo para el cálculo de cubiertas convexas en 3D.

Fecha de entrega: 19 de febrero del 2013 antes de las 12h00 		.
- 15/02/13 Examen 1 .
- 19/02/13 Revisión Examen 1 .
10 22/02/13 Intersección de segmentos de línea, 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 y su aplicación práctica a la solución de uno de los siguientes problemas: (a) superposición de dos subdivisiones del plano, (b) operaciones Booleanas sobre dos polígonos. Prepare además un reporte (en Latex) donde se expliquen los detalles de la implementación realizada, los resultados experimentales de sus pruebas, así como un análisis de la complejidad de su implementación del algoritmo.

Fecha de entrega: 8 de marzo del 2013 antes de las 12h00 		.
11 26/02/13 Triangulación de polígonos
Tarea 7: Implementación del algoritmo de triangulación de polígonos visto en clase y su aplicación práctica a la solución del problema de la galeria de arte descrito en la sección 3.1 del libro de Berg et al. Prepare también un reporte (en Latex) donde se presenten los detalles de la implementación realizada, así como resultados de los experimentos efectuados para probar el desempeño de su algoritmo.

Fecha de entrega: 22 de marzo del 2013 antes de las 12h00 		.
Tarea 8: Utilizando la siguiente plantilla prepare una presentación que cubra el material del capítulo 5 u 8 del libro de Berg et al.

Fechas de entrega: 8 y 19 de marzo
12 01/03/13 Intersección de semiplanos
13 05/03/13 Programación lineal
Algunos ejemplos de PL:
  1. http://www.programacionlineal.net/programacion_lineal.html
  2. http://es.scribd.com/doc/21066515/Ejercicios-Programacion-Lineal
  3. http://actividadesinfor.webcindario.com/proli.htm
 .
Entrega de propuestas para proyectos finales .
14 08/03/13 Búsqueda de rango ortogonal
15 12/03/13 Localización de puntos en el plano
Elección de propuestas para proyectos finales .
16 15/03/13 Diagramas de Voronoi
17 19/03/13 Arreglos y dualidad
18 22/03/13 Triangulaciones de Delaunay
Tarea 9: Implementar los dos algoritmos para construcción del árbol euclidiano de cobertura mínimo expuestos en la sección 7.4 de los apuntes de J. Chen que pueden encontrarse en la siguiente dirección:
Las dos implementaciones deben contar con una interfaz gráfica que permita visualizar los puntos de entrada y los árboles resultantes. Prepare además un reporte (en Latex) donde se expliquen los detalles de las implementaciones realizadas, un análisis de los dos algoritmos en cuanto a su desempeño con respecto al escalamiento del tamaño de las instancias de prueba generadas aleatoriamente, así como una comparativa de desempeño de ambos algoritmos sobre casos de prueba que fuercen el algoritmo de Kruskal a su peor caso.

Fecha de entrega: 5 de abril del 2013 antes de las 12h00 		.
- 16/04/13 Examen 2 .
- 23/04/13 Entrega del proyecto final .



® 2008 Eduardo Rodriguez-Tello