Geometría Computacional, agosto-diciembre 2024
Información del curso
Libros de texto:
Computational Geometry: Algorithms and Applications. M de Berg, O Cheong, M van Kreveld, M Overmars.Third Edition. Computational Geometry in C. Joseph O'Rourke. Second Edition.Horario: Miércoles y Viernes de 10 a 12 hrs.
Horas de oficina: Jueves 4:30 - 5:30
Tareas
Tarea 5. Errata: el pdf marca Tarea 3, pero en realidad es la Tarea 5.
Proyectos
Calendario
Viernes 30 de agosto: Presentación del curso: ¿Qué es la Geometría Computacional? Notas.
Miércoles 4 de septiembre: Background. Objetos geométricos básicos. Notas.
Viernes 6 de septiembre: Test de orientación. Notas. Lectura sugerida: O'Rourke, Sección 1.5.
Miercoles 11 de septiembre:
1. Notación asintótica. Lecture sugerida: Cormen Capítulo 3.
2. Definiciones de convexidad. Lectura sugerida: O'Rourke Sección 3.1.
3. Problemas básicos con
polígonos. Notas de la Dra. Vera Sacristán.
Viernes 14 de septiembre: Terminamos: Problemas básicos con polígonos.
Miércoles 18 de septiembre: Ahora sí terminamos: Problemas básicos con polígonos. Presentación usada en clase. Lectura sugerida: O'Rourke 7.1,7.2,7.4
Viernes 22 de septiembre: Cierres convexos, parte uno. Presentación usada en clase.Lectura sugerida: O'Rourke Capitulo 3.
Miércoles 25 de septiembre: Cierres convexos, parte dos.
Viernes 26 de septiembre: Cierres convexos, parte tres y final. Presentación usada en clase. Se asignó la Tarea 1.
Miércoles 2 de Octubre: Intersección de segmentos: Algoritmo Bentley-Ottmann. Presentación usada en clase. Lectura sugerida: Mark de Berg Capítulo 2.
Viernes 4 de Octubre: Intersección de segmentos, parte 2.Lectura sugerida: Mark de Berg Capítulo 2. Se asignó la Tarea 2.
Miércoles 9 de Octubre: Gráficas: conceptos básicos y planaridad.
Viernes 11 de Octubre: Encajes planos. Programamos el Primer Parcial para el día Miércoles 23 de Octubre en el horario de clase.
Miércoles 16 de Octubre: DCEL. Se asignó la Tarea 3.
Viernes 18 de Octubre: se resolvieron dudas para preparar el examen.
Miércoles 23 de Octubre: Examen Parcial 1.
Viernes 25 de Octubre: Triangulación de polígonos. Presentación usada en clase
Miércoles 30 de Octubre: Triangulación de polígonos. Presentacion usada en clase.
Viernes 1 de Noviembre: suspendimos clase por celebración de Día de Muertos.
Miércoles 6 de Noviembre: Triangulación de polígonos monótonos. Presentación usada en clase.
Viernes 8 de Noviembre: Partición del polígono en piezas monótonas. Presentación usada en clase, ver nota al final.
Miércoles 13 al Viernes 22 de Noviembre: kd-trees, búsqueda de rangos y range trees. Notas kd-trees. Notas range trees.
Miércoles 27 de Noviembre: problemas de proximidad. Usamos la presentación de la Dra. Vera Sacristán.
Viernes 29 de Noviembre: terminamos problemas de proximidad e iniciamos algoritmos para calcular el Diagrama de Voronoi.
Otros recursos
Robustness Problems in Geometric Computations
El curso de Geometría Computacional de la Dra. Vera Sacristán