- ES Español (Latinoamérica)

- EN English

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.
| Área de Conocimiento (KA) | Core Tier1 | Core Tier2 |
4.9.1 Diagramas de Voronoi y Triangulaciones de Delaunay | 1 | 1 |
4.9.2 Envolventes Convexas y Politopos | 1 | 1 |
4.9.3 Topología Digital y Análisis de Imágenes | 1 | 1 |
4.9.4 Homología Persistente y Topología Aplicada | 1 | 1 |
4.9.5 Generación de Mallas y Algoritmos Geométricos | 1 | 1 |
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:
- Describir la dualidad entre el diagrama de Voronoi y la triangulación de Delaunay y demostrar la propiedad de la circunferencia vacía [Familiarizarse]
- Construir diagramas de Voronoi y triangulaciones de Delaunay usando el algoritmo de Fortune y analizar su complejidad [Usar]
- 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:
- Comparar la complejidad temporal del escaneo de Graham, la marcha de Jarvis y el algoritmo de Chan e identificar casos óptimos [Familiarizarse]
- Implementar un algoritmo de envolvente convexa 2D y extenderlo a la construcción incremental 3D [Usar]
- 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:
- Explicar la adyacencia digital y por qué una conectividad inconsistente conduce a paradojas topológicas [Familiarizarse]
- Aplicar algoritmos de thinning y skeletonización para extraer características estructurales de imágenes binarias [Usar]
NonCore:
- 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:
- Calcular grupos de homología simplicial y números de Betti a partir de un complejo simplicial [Familiarizarse]
- 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:
- 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:
- Explicar la estrategia de refinamiento de Delaunay y el papel de los puntos de Steiner para lograr garantías de calidad [Familiarizarse]
- Generar una triangulación de Delaunay restringida de calidad para un dominio planar dado usando el algoritmo de Ruppert [Usar]
NonCore:
- 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]