Inicio
Contacto
Mapa del sitio
Directorio
Correo
Tienda Virtual
IngresarCiencias de la Computación (plan 1994) 2023-2
Optativas, Geometría Computacional
| Profesor | Adriana Ramírez Vigueras | lu mi vi | 11 a 12 | Taller de Computación Visual e Innovación Tecnológica |
| Ayudante | Fhernanda Montserrat Romo Olea | ma ju | 11 a 12 | Taller de Computación Visual e Innovación Tecnológica |
| Ayud. Lab. | Marco Antonio Velasco Flores | ma | 16 a 18 | Taller de Lenguajes de Programación |
Temario
1.Introducción
1.1 Definiciones Generales.
1.2 Estructuras de datos.
1.3 Preliminares Geométricos.
2. Cierre Convexo de un conjunto de puntos en R^2.
2.1 Cota mínima.
2.2 Algoritmo de Graham.
2.3 Algoritmo de Jarvis.
2.4 Algoritmos usando divide y venceras.
2.5 Algoritmos dinámicos.
2.6 Extensiones y variantes.
3. Intersecciones entre segmentos de rectas.
3.1 Detección.
3.2 Lista doblemente conexa de aristas.
3.3 Calculando el traslape de dos subdivisiones.
4. Triangulación de polígonos.
4.1 Vigilancia y triangulaciones.
4.2 Dividiendo un polígono en piezas monótonas.
4.3 Triangulando un polígono monótono.
5. Programación lineal.
5.1 La geometría de amoldado.
5.2 Intersección de semiplanos.
5.3 Círculo contenedor de radio mínimo.
5.4 Programación lineal incremental.
5.5 Programación linal aleatoria.
5.6 Programación lineal en dimensiones superiores.
6. Búsqueda de rangos ortogonales.
6.1 Búsqueda en una dimensión.
6.2 Árboles Kd
6.3 Árboles de rangos.
7. Localización de puntos.
7.1 Localización de un punto en una subdivisión plana.
7.2 Método de bandas.
7.3 Método de cadena.
7.4 Método trapezoidal.
7.5 Algoritmo incremental aleatorio.
8. Diagramas de Voronoi.
8.1 Definición y propiedades básicas.
8.2 Construyendo el diagrama de Voronoi.
8.3 Cota mínima.
8.4 Aplicaciones.
9. Arreglos de líneas y Dualidad.
9.1 Arreglos de líneas.
9.2 Dualidad.
9.3 Triangulación de Delaunay.
10. Proximidad: Variantes y Generalizaciones.
10.1 Par de puntos más cercanos.
10.2 Par de puntos más lejanos.
10.3 Árboles generadores mínimos euclideanos.
10.4 Diagramas de Voronoi de orden superior.
11. Algunas estructuras de datos geométricas.
11.1 Árboles de intervalos
11.2 Árboles de prioridades y búsqueda
11.3 Árboles de segmentos
12. Algunos resultados importantes de geometría discreta.
12.1 Ham Sandwich.
12.2 Erd ̈os - Szekeres.
Bibliografía.
Básica.
1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry (3rd ed.), Springer Verlag, Berlin, 2008.
2. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985.
3. Joseph O’Rourke. Computational Geometry in C (2nd ed.). Cambridge University Press, 1998.
4. S. Devadoss and J. O’Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.
Complementaria.
1. J. R. Sack and J. Urrutia, Editores. Handbook of Computational Geometry. Elsevier, 1997.
2. S. Ghosh. Visibility Algorithms in the Plane. Cambridge: Cambridge University Press, 2007.
3. F. P. Preparata and M. I. Shamos. Computational Geometry: An Introduction. Springer-Verlag, New York, NY, 1985.
Dinámica del curso:
Se compartirá material usando Google Classroom.
Las tareas se entregarán usando Google Classroom en formato pdf.
Favor de verificar su correo registrado en el sistema de la facultad, porque usaremos la lista de correos que la facultad proporciona a los profesores para crear el Classroom.
Sistema de calificaciones:
Tareas examen y prácticas 75 %.
Exposición 25 %.
La exposición es obligatoria para acreditar el curso y obtener al menos 6 en tareas examen
Facebook
Twitter
Youtube