Responsable: José Miguel Díaz Báñez
Tipo de Proyecto/Ayuda: Plan Nacional del 2009
Referencia: MTM2009-08625
Fecha de Inicio: 01-01-2010
Fecha de Finalización: 31-12-2012

Empresa/Organismo financiador/es:

• Ministerio de Ciencia e Innovación

Equipo:

• Investigadores:
  • Sergey Bereg
  • Manuel Heredia Zapata
  • Pablo Pérez Lantero
  • Jorge Urrutia Galicia
  • Inmaculada Ventura Molina

Resumen del proyecto:

Un problema de optimización geométrica es un problema de optimización inducido por una colección de objetos geométricos. Los algoritmos geométricos que resuelven problemas de optimización poseen multitud de aplicaciones. Se estudian tanto desde el punto de vista teórico en geometría computacional como aplicado en investigación operativa, robótica, gráficos por computador o sistemas de información geográfica. En geometría computacional se enfoca el estudio de algoritmos eficientes para versiones abstractas de los problemas, pudiendo ser exactos o de aproximación. Sin embargo, en algunas áreas de aplicación los problemas son menos abstractos y los algoritmos más heurísticos, esto es, no se da una prueba teórica de la bondad del procedimiento.

Formulaciones y resoluciones geométricas son bien conocidas para muchos problemas de decisión y optimización en localización de servicios, minería de datos, reconocimiento de formas, etc. En este proyecto se abordan problemas de optimización explorando su resolución desde distintos puntos de vista desde los cuales el problema puede plantearse, diseñando algoritmos y analizando su eficiencia y, en su caso, probando el factor de soluciones aproximadas. Los problemas de optimización geométrica son con frecuencia NP-duros y en tal caso, se explorarán tanto heurísticos como algoritmos de aproximación. La investigación estará enfocada a tres clases de problemas que provienen de tres áreas emergentes de aplicación. Dichas áreas contienen una gran variedad de tipos de problemas de gran interés tanto teórico como práctico.

Las colecciones de problemas están organizados según tres subproyectos o líneas de investigación. La primera hace referencia a problemas de clasificación y aprendizaje computacional. La segunda línea plantea problemas que aparecen en el estudio del diseño de redes de comunicación, donde se desea optimizar la prestación de la misma.

Finalmente, la tercera colección de problemas proviene de un campo de reciente interés como es la robótica aérea en aeronáutica, donde el problema de resolución de colisiones resulta esencial cuando aumenta la densidad del tráfico aéreo. Así, el objetivo principal de este proyecto es avanzar en el conocimiento y resolución de este tipo de problemas utilizando la sinergia existente entre las áreas de geometría computacional e investigación operativa.