Universidad Politécnica de Madrid

ACCIÓN COMPLEMENTARIA AL09-PAC-12 METAHEURÍSTICAS PARA LA RESOLUCIÓN APROXIMADA DE PROBLEMAS GEOMÉTRICOS

Universidad Nacional de San Luis

La Geometría Computacional estudia el diseño y análisis de algoritmos para resolver problemas geométricos. Los problemas de este tipo aparecen en múltiples áreas de la Computación, tales como Computación Gráfica, Planificación de Movimientos, Visión Computacional, Robótica, Diseño VLSI, Recuperación de la Información, Bases de Datos espacio-temporales, etc. Una buena introducción se puede consultar en  este enlace.

 
Muchos problemas en esta área son NP-duros, por lo que se precisa de soluciones aproximadas a los problemas. Las metaheurísticas constituyen una herramienta adecuada para este tipo de soluciones,   pues se pueden aplicar a muchos problemas sin la necesidad de desarrollar herramientas ad-hoc para cada uno de ellos. Las líneas de investigación en las que se está trabajando en el grupo son las siguientes:

• Optimización de triangulaciones planas.
• Indexación espacio-temporal sobre objetos en movimiento
• Aplicación de metaheurísticas para la resolución aproximada de problemas NP-duros para triangulaciones planas.
• Optimización de rutas de vigilancia entre obstáculos poligonales.
• Metaheurísticas para problemas de dilación en redes geométricas