Ciencias de la Computación (plan 1994) 2016-2
Optativas, Geometría Computacional
Grupo 7011, 30 lugares. 8 alumnos.
Lab: ma 16 a 18 Taller de Lenguajes de Programacion
Temario
Introducción
[1.1] Definiciones Generales.
[1.2] Estructuras de datos.
[1.3] Preliminares Geométricos.
Cierre Convexo de un conjunto de puntos en el plano.
[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.
Intersecciones entre segmentos de rectas.
[3.1] Detección.
[3.2] Lista doblemente conexa de aristas.
[3.3] Calculando el traslape de dos subdivisiones.
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.
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.
Búsqueda de rangos ortogonales.
[6.1] Búsqueda en una dimensión.
[6.2] Árboles Kd.
[6.3] Árboles de rangos.
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.
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.
Arreglos de líneas y Dualidad.
[9.1] Arreglos de líneas.
[9.2] Dualidad.
[9.3] Triangulación de Delaunay.
...
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.
4. J. R. Sack and J. Urrutia, Editores. Handbook of Computational Geometry. Elsevier, 1997.
5. S. Devadoss and J. O'Rourke. Discrete and Computational Geometry. Princeton University Press, 2011.
Evaluación
NO Examenes - Tareas examen 50%
Dos o tres proyectos - Prácticas 30%
Exposición 20%
![](http://www.ufunk.net/wp-content/uploads/2012/08/Triangulations-Portraits-by-Josh-Bryan-2.jpg)
![](http://xochitl.matem.unam.mx/~adriana/images/IMG_0015.JPG)
![](http://xochitl.matem.unam.mx/~adriana/images/IMG_0016.JPG)
![](http://xochitl.matem.unam.mx/~adriana/images/IMG_0017.JPG)
![](http://grmanet.sogang.ac.kr/media/results/rendering/enhancing_speed/image/SPFig2.jpg)
![](http://www.nature.com/nprot/journal/v4/n7/images/nprot.2009.94-F3.jpg)
![](https://c2.staticflickr.com/4/3225/3141700346_8d912ce618.jpg)