Geometría Computacional en el plano.
Profesor: Dr. Francisco Rivero Mendoza.

 

Motivación.

La Geometría Computacional es una nueva rama dentro de las Ciencias de la Computación, que tuvo su origen en la tesis de Ph. D. de Michael Shamos en la Universidad de Yale en 1978. Se trata de buscar y analizar algoritmos eficientes para resolver  problemas geométricos que surgen en distintos campos como la robótica, inteligencia artificial, redes neuronales y otros, que se han desarrollado vigorosamente con la aparición de computadoras cada vez más versátiles y potentes. Es una disciplina esencialmente constructiva, de carácter abstracto, que utiliza técnicas de la geometría clásica,  la topología, teoría de grafos, teoría de conjuntos y el álgebra lineal. La geometría computacional es independiente de la tecnología de las máquinas de computación.

 

Objetivos:

1. Iniciar al estudiante al estudio de temas de matemáticas aplicadas que puedan ampliar su formación.
2. Iniciar al estudiante en temas de investigación en el área de la computación.
3. Revisar conocimientos básicos de geometría.
4. Desarrollar las habilidades para construir algoritmos de tipo geométrico  y su implementación en lenguaje C.
5. Crear la conciencia de trabajo interdisciplinario.

 

Prerrequisitos.

1.      Cursos básicos de Álgebra Lineal, Topología, Programación Digital y matemáticas discretas (opcional).

2.      Buena dosis de comprensión hacia las técnicas y métodos de una nueva disciplina.

 

Programa del curso.

Capítulo 1 Introducción

1.1. ¿Qué es la geometría computacional?

1.2. Algunos ejemplos importantes

1.2.1. Área de un triangulo

1.2.2. La Envolvente Convexa

1.2.3. Polígonos

1.2.4. Un Algoritmo Intuitivo

1.2.5. Complejidad

1.2.6. El problema del robot

1.3. Problemas de localización de servicios

1.3.1. Un problema muy viejo

1.4. El problema del círculo mínimo

 

Capítulo. 2 Triangulaciones

2.1. Problema de la galería de arte

2.2. Coloración de Grafos

2.3. Demostración del teorema de Chvátal

2.4. Algoritmos de triangulación

2.4.1. Listas doblemente enlazadas

2.4.2. Implementación.

 

Capítulo3. La envolvente convexa

3.1. Algoritmo de envolvimiento de regalo

3.2. Algoritmo De Graham

3.2.1. Descripción del Algoritmo

3.2.2. La Pila

3.2.3. Código para el algoritmo

3.3. El algoritmo QUICK-HULL

3.4. El método Divide y Vencerás

3.4.1. Algoritmo Divide y Vencerás

 

Capítulo 4. Diagrama de Voronoi

4.1. Problemas de Aproximación

4.2. El Diagrama de Voronoi

4.2.1. Definiciones básicas

4.2.2. Propiedades del diagrama de Voronoi

4.2.3. Diagrama de Voronoi y la Envolvente Convexa

4.3. Construcción del Diagrama de Voronoi

4.3.1. Concatenación: Aspectos claves

4.3.2. El grafo frontera

4.3.3. Un algoritmo para construir la frontera

4.4. Aplicaciones

4.4.1. El vecino más cercano

4.4.2. Los pares más cercanos

4.4.3. Problema del Máximo Círculo Vacío

4.4.4. Triangulación de Delauny

 

Notas del Curso: Archivo en PDF

Enlaces de interés:

Página del DR. Manuel Abellanas de La facultad de Infórmática de la Universidad  Politécnica de Madrid

 

 

Bibliografía:

1. J. Chen. Computational Geometry: Methods and Applications. Texas A&M University. 1996.
2. F.P. Preparata y M.I. Shamos, Computational Geometry: An Introduction, Springer – Verlag, New York, (1985).
3. J. O’Rourke, Computational Geometry in C, Cambridge University Press. 1997.