Planificación de Geometría Computacional (2018)

Definición y alcances de la Geometría Computacional.

Conceptos previos:

Series numéricas

Elementos de la Topología: Abierto, Espacio Topológico, Entorno, Frontera, Conexidad, Compacidad, Homeomorfismo, Variedades diferenciales.

Espacios y transformaciones: Vectorial, Afín, Proyectivo, Métricas. Coordenadas en símplices y funciones de forma.

Análisis Asintótico y Complejidad algorítmica: Cotas O, o, Ω, ω y θ; Análisis de recursiones y Master Theorem.

Dualidades: Grafos duales. Incidencia. Dualidad punto/linea: Dualidad Algebraica. Inversión circular – Polaridad. Dualidad Proyectiva y polaridad cónica.111

Clasificación de polígonos: Simple/Autointerceptado. Convexo/Estrella/Visible desde el exterior. Monótono respecto a una línea.

Definiciones equivalentes de Envoltorio Convexo.

Algoritmo O(n³) trivial.

Algoritmos O(n log(n)): Incremental: Graham Scan. Divide and Conquer. Quick Hull

Algoritmos output-dependent: O(nh): Gift Wrapping y Jarvis March. O(n log(h)): Algoritmo de Chan

Búsqueda en O(log(n)) de tangentes y Bounding-Box de polígonos convexos.

Algoritmo de barrido plano y estructuras de datos asociadas: Cola de Eventos. Árboles Binarios Auto-Balanceados. Lista Doblemente Enlazada de aristas.

Operaciones Booleanas entre grafos (mallas) y regiones planas (GIS)

Problema del guardián de la galería de arte y triangulaciones. Art Gallery Theorem.

Partición de un polígono en piezas monótonas: Algoritmo de barrido. Triangulación de polígonos monótonos en tiempo lineal.

Triangulación de polígonos con fronteras interiores, regiones planas con líneas sueltas y nubes de puntos aislados.

Desmoldabilidad de poliedros y chapas estampadas.

Intersección de semiplanos: Algoritmo divide and conquer.

Programación lineal: Algoritmo incremental. Justificación y backwards analysis para los Algoritmos Aleatorios: Expected Time. Unbounded Linear Programs. Programación lineal en muchas dimensiones

Problemas parecidos o LP-type problems: Facility planning, Euclidean 1-center o envoltorio esférico. Normales y mínimo casquete envolvente en la esfera unitaria.

Bases de datos y el problema 1D.

Búsqueda ortogonal.

Trees y Tries: kD Tree. Octree. BSP tree.

Búsqueda en triangulaciones por funciones de forma.

Definiciones y dualidad, propiedades.

Algoritmo de Fortune: lifting map y coastline.

Triangulación incremental aleatoria.

Generación de puntos y mallas.

Algoritmos en 3D.

Algoritmos en muchas dimensiones.

M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars
Computational Geometry: Algorithms and Applications
Springer-Verlag