Encabezado Facultad de Ciencias
Presentación

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

Optativas, Geometría Computacional

Grupo 7012, 30 lugares. 9 alumnos.
Profesor Adriana Ramírez Vigueras lu mi vi 13 a 14 P104
Ayudante Javier Cano Vila ma ju 13 a 14 P104

 

Geometría Computacional

Objetivo. Este curso ofrece una introducción al área de la geometría computacional con el fin de conocer y entender los conceptos, técnicas, algoritmos y estructuras de datos dentro del área.
Cada tema será estudiado a partir de un problema geométrico, que sea altamente aplicable en la vida real.
Al finalizar el curso el alumno habrá adquirido los conocimientos necesarios, en el área de la geometría computacional, para diseñar algoritmos eficientes que resuelvan problemas computacionales que requieran soluciones geométricas.

Contenido Temático

Introducción
  1. ​Definiciones Generales.
  2. Estructuras de datos.
  3. Preliminares Geométricos
Cierre Convexo de un conjunto de puntos en el plano.
  1. Cota mínima.
  2. Algoritmo de Graham.
  3. Algoritmo de Jarvis.
  4. Algoritmos usando divide y venceras.
  5. Algoritmos dinámicos.
  6. Extensiones y variantes.
Intersecciones entre segmentos de rectas.
  1. Detección.
  2. Lista doblemente conexa de aristas.
  3. Calculando el traslape de dos subdivisiones.
  4. Barrido Topológico.
  5. Ordenando pendientes en O(n²).
Triangulación de polígonos.
  1. Vigilancia y triangulaciones.
  2. Dividiendo un polígono en piezas monótonas
  3. Triangulando un polígono monótono.
Programación lineal
  1. ​La geometría de amoldado.
  2. Intersección de semiplanos.
  3. Círculo contenedor de radio mínimo.
  4. Programación lineal incremental.
  5. Programación lineal aleatoria.
  6. Programación lineal en dimensiones superiores.
Búsqueda de rangos ortogonales.
  1. Búsqueda en una dimensión.
  2. Arboles Kd.
  3. Arboles de rangos.
Localización de puntos.
  1. Localización de un punto en una subdivisión plana.
  2. Método de bandas.
  3. Método de cadena.
  4. Método trapezoidal.
  5. Algoritmo incremental aleatorio.
Diagramas de Voronoi.
  1. Definición y propiedades básicas.
  2. Construyendo el diagrama de Voronoi.
  3. Cota mínima.
  4. Aplicaciones.

Arreglos de líneas y Dualidad.

  1. Arreglos de líneas.
  2. Dualidad.
  3. Triangulación de Delaunay.
Proximidad: Variantes y Generalizaciones.
  1. Par de puntos más cercanos.
  2. Par de puntos más lejanos.
  3. Arboles generadores mínimos euclideanos.
  4. Triangulación plana.
  5. Triangulación glotona.
  6. Diagramas de Voronoi de orden superior.

Estructuras Geométricas Avanzadas.

  1. Árboles de intervalos.
  2. Árboles de prioridades y búsqueda.
  3. Árboles de segmentos.

*Algunos resultados importantes de geometría discreta.

  1. Ham Sandwich.
  2. Erdös - Szekeres.
Bibliografía
  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.

 


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.