Encabezado Facultad de Ciencias
Presentación

Ciencias de la Computación (plan 1994) 2014-2

Optativas, Geometría Computacional

Grupo 7011, 30 lugares. 8 alumnos.
Laboratorio los lunes de 14 a 16 horas en Aula de Ciencias de la Computación 2
Profesor Adriana Ramírez Vigueras lu mi vi 13 a 14 P118
Ayudante Ricardo López López ma ju 13 a 14 P118
Ayud. Lab. José Emiliano Cabrera Blancas lu 14 a 16 Laboratorio de Ciencias de la Computación 2

 
Temario de Geometría Computacional

Profesora: Adriana Ramírez Vigueras

Ayudante: Ricardo López López

Ayudante Lab: José Emiliano Cabrera Blancas

Semestre 2014-II

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 R2.

2.1 Cota mínima.
2.2 Algoritmo de Graham.
2.3 Algoritmo de Jarvis.
2.4 Algoritmos usando divide y vencéras.

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 ́etodo 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 - Szekers.

Bibliografía. Básica.

  1. M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geo- metry (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.

Complementaria.

  1. J. R. Sack and J. Urrutia, Editores. Handbook of Computational Geometry. Elsevier,

    1997.

  2. S. Devadoss and J. O’Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.

Evaluación.

Tareas examen 50 %.
Prácticas 30 %.
Exposición 20 %.
La exposición es obligatoria para acreditar el curso.

No se aceptan tareas por correo electrónico.

 


Hecho en México, todos los derechos reservados 2011-2016. Esta página puede ser reproducida con fines no lucrativos, siempre y cuando no se mutile, se cite la fuente completa y su dirección electrónica. De otra forma requiere permiso previo por escrito de la Institución.
Sitio web administrado por la Coordinación de los Servicios de Cómputo de la Facultad de Ciencias. ¿Dudas?, ¿comentarios?. Escribenos. Aviso de privacidad.