Home

Geometría Computacional

Geometría Computacional

Objetivo

En este curso se estudiarán los conceptos básicos de la Geometría Computacional (GC) así como sus aplicaciones. El material aborda las técnicas necesarias para el diseño y análisis de algoritmos eficientes para resolver problemas en geometría, tales como: cubiertas convexas (convex hulls), intersecciones geométricas, diagramas de Voronoi, triangulaciones de Delaunay, estructuras de datos geométricas, etc.

 

Contenido

  1. Introducción a la GC

  1. Qué es la GC

  2. Ejemplo de un problema típico de GC

  3. Limitaciones de la GC

  4. Tendencias de la GC

  5. Dominios de aplicación

 

  1. Cubiertas convexas

  1. Algoritmo de Graham

  2. Algoritmo de Chan

  3. Algoritmo QuickHull

 

  1. Intersección de segmentos de línea

  1. Intersecciones geométricas

  2. Intersección de segmentos de línea

  3. Algoritmo de barrido del plano (plane-sweep)

  4. Representación e intersección de subdivisiones planares

 

  1. Triangulación de polígonos

  1. Grafos planares

  2. El problema de la galería de arte

  3. Partición de un polígono es sus piezas monótonas

  4. Triangulación de polígonos monótonos

 

  1. Programación lineal

  1. Intersección de sub-planos (half-plane)

  2. Algoritmo divide y venceras

  3. Algoritmo determinístico incremental

  4. Algoritmo aleatorio

 

  1. Búsqueda de rango ortogonal

  1. Consultas de rango en una dimensión

  2. Árboles kd

  3. Árboles de rango

  4. Árboles de rango en dimensiones mayores

  5. Conjuntos generales de puntos

 

  1. Localización de puntos en el plano

  1. El método de Kirkpatrick

  2. Descomposiciones trapezoidales

  3. Estructuras de datos para localización de puntos

 

  1. Diagramas de Voronoi

  1. Definición y propiedades básicas

  2. Construcción de diagramas de Voronoi

  3. Algoritmo divide y venceras

  4. Algoritmo aleatorio incremental

  5. Algoritmo de Fortune

 

  1. Arreglos de líneas y dualidad

  1. Cálculo de la discrepancia

  2. Dualidad

  3. Construcción incremental de arreglos

  4. Niveles y discrepancia

 

  1. Triangulación de Delaunay

  1. Triangulación de conjuntos de puntos

  2. Propiedades de la triangulación de Delaunay

  3. Construcción incremental

 

Bibliografía

1. Mark de Berg, Otfried Cheong, Marc van Kreveld and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer, 3rd edition (April 16, 2008), ISBN-10: 3540779736.

2. Joseph O’Rourke. Computational Geometry in C. Cambridge University Press; 2000 edition (February 15, 2001), ISBN-10: 0521649765.

3. Jacob E. Goodman and Joseph O’Rourke (editors). Handbook of Discrete and Computational Geometry. Chapman & Hall/CRC, 2nd edition (April 15, 2004), ISBN-10: 1584883014.

4. Franco P. Preparata and Michael Ian Shamos. Computational Geometry an Introduction. Springer, (August 6, 1993), ISBN-10: 0387961313.

 

  • share