4.9. Geometría y Topología Computacional (CGT)

4.9. Geometría y Topología Computacional (CGT)

Esta área cubre algoritmos geométricos y métodos topológicos para procesar datos espaciales discretos, incluyendo estructuras de Voronoi, envolventes convexas, generación de mallas, topología digital y homología persistente aplicada, con aplicaciones a gráficos por computadora, robótica y computación científica.

Tabla 4.9: Lista de KUs del área de Geometría y Topología Computacional.

4.9.1. CGT/Diagramas de Voronoi y Triangulaciones de Delaunay  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba

Diagramas de Voronoi, triangulaciones de Delaunay, dualidad, algoritmos y aplicaciones en computación espacial.
Temas:
Core

  • Diagrama de Voronoi: definición, complejidad combinatoria y propiedades en \(\mathbb{R}^d\)
  • Triangulación de Delaunay: propiedad de la circunferencia vacía y dualidad con Voronoi
  • Algoritmos: algoritmo de la línea de barrido de Fortune y construcción incremental aleatorizada
  • Diagramas de Voronoi ponderados y diagramas de potencia
  • Aplicaciones: búsqueda del vecino más cercano, planificación de trayectorias y generación de mallas

Aprendizaje esperado (Learning Outcomes):
Core:

  1. Describir la dualidad entre el diagrama de Voronoi y la triangulación de Delaunay y demostrar la propiedad de la circunferencia vacía [Familiarizarse]
  2. Construir diagramas de Voronoi y triangulaciones de Delaunay usando el algoritmo de Fortune y analizar su complejidad [Usar]
  3. Aplicar triangulaciones de Delaunay a la generación de mallas y consultas de vecino más cercano en conjuntos de datos espaciales [Evaluar]

4.9.2. CGT/Envolventes Convexas y Politopos  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba

Algoritmos de envolvente convexa en 2D y 3D, politopos convexos, consultas de puntos extremos e intersección de semiespacios.
Temas:
Core

  • Algoritmos de envolvente convexa 2D: escaneo de Graham, marcha de Jarvis y algoritmo de Chan
  • Envolvente convexa 3D: construcción incremental y algoritmos aleatorizados
  • Politopos convexos: retículo de caras, relación de Euler y teorema de la cota superior
  • Intersección de semiespacios y dualidad entre envolvente convexa y problemas de semiespacios
  • Aplicaciones: programación lineal, detección de colisiones y análisis de formas

Aprendizaje esperado (Learning Outcomes):
Core:

  1. Comparar la complejidad temporal del escaneo de Graham, la marcha de Jarvis y el algoritmo de Chan e identificar casos óptimos [Familiarizarse]
  2. Implementar un algoritmo de envolvente convexa 2D y extenderlo a la construcción incremental 3D [Usar]
  3. Aplicar la dualidad entre envolvente convexa e intersección de semiespacios para resolver problemas de programación lineal geométricamente [Evaluar]

4.9.3. CGT/Topología Digital y Análisis de Imágenes  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba

Propiedades topológicas de imágenes digitales, componentes conexas, esqueletización, skeletonización y persistencia topológica en datos de imagen.
Temas:
Core

  • Adyacencia digital, conectividad y el teorema de la curva de Jordan para imágenes digitales
  • Etiquetado de componentes conexas e invariantes topológicos de imágenes binarias
  • Algoritmos de thinning y skeletonización del eje medial
  • Característica de Euler de objetos digitales y su cálculo a partir de patrones locales

Non Core

  • Métodos topológicos para segmentación de imágenes y reconstrucción de superficies a partir de nubes de puntos

Aprendizaje esperado (Learning Outcomes):
Core:

  1. Explicar la adyacencia digital y por qué una conectividad inconsistente conduce a paradojas topológicas [Familiarizarse]
  2. Aplicar algoritmos de thinning y skeletonización para extraer características estructurales de imágenes binarias [Usar]

NonCore:

  1. Calcular invariantes topológicos (característica de Euler, números de Betti) de un objeto digital y usarlos para clasificación de formas [Evaluar]

4.9.4. CGT/Homología Persistente y Topología Aplicada  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba

Homología simplicial, filtraciones, módulos de persistencia, códigos de barras y aplicaciones al análisis de formas y datos.
Temas:
Core

  • Homología simplicial: grupos de cadenas, operadores borde y números de Betti
  • Módulos de persistencia y el teorema de estructura para descomposición en módulos de intervalo
  • Códigos de barras y diagramas de persistencia: pares nacimiento-muerte y vida topológica
  • Algoritmos para homología persistente: algoritmo de reducción de matriz de incidencia

Non Core

  • Aplicaciones: plegamiento de proteínas, ciencia de materiales y neurociencia (2020-2025)

Aprendizaje esperado (Learning Outcomes):
Core:

  1. Calcular grupos de homología simplicial y números de Betti a partir de un complejo simplicial [Familiarizarse]
  2. Construir una filtración a partir de una nube de puntos y calcular su diagrama de persistencia mediante reducción de matriz de incidencia [Usar]

NonCore:

  1. Interpretar códigos de barras de datos reales y explicar las características topológicas que revelan en un contexto científico [Evaluar]

4.9.5. CGT/Generación de Mallas y Algoritmos Geométricos  (Core Tier1: 1 hr, Core Tier2: 1 hr) ↑ Volver arriba

Generación de mallas triangulares y tetraédricas, refinamiento de Delaunay, métricas de calidad y algoritmos para subdivisión espacial.
Temas:
Core

  • Métricas de calidad de malla: relación de aspecto, ángulo mínimo y relación circunradio-arista más corta
  • Refinamiento de Delaunay: algoritmo de Ruppert y algoritmo de Shewchuk para generación de mallas de calidad
  • Generación de mallas tetraédricas: tetraedralización de Delaunay restringida y puntos de Steiner
  • Mallado dominante por cuadriláteros y hexaedros: métodos de campo cruzado y mallas poliédricas

Non Core

  • Refinamiento adaptativo de malla guiado por estimadores de error en simulaciones de elementos finitos

Aprendizaje esperado (Learning Outcomes):
Core:

  1. Explicar la estrategia de refinamiento de Delaunay y el papel de los puntos de Steiner para lograr garantías de calidad [Familiarizarse]
  2. Generar una triangulación de Delaunay restringida de calidad para un dominio planar dado usando el algoritmo de Ruppert [Usar]

NonCore:

  1. Diseñar una estrategia de refinamiento adaptativo de malla para un problema de EDP y justificar los criterios de refinamiento basados en estimaciones de error a posteriori [Evaluar]

¿Encontraste una errata, un curso desactualizado, un enlace roto, o tienes una sugerencia? Cuéntanos.

Escanea para abrir en tu teléfono