Incremento del tamaño del espacio de soluciones factibles para SMINK-1 usando algoritmos evolutivos

Abstract

En este trabajo de investigación estudiamos la suma de Minkowski. Hemos estudiado su contexto teórico, propiedades geométricas y aplicaciones más destacadas. Además, hemos implementado la suma de Minkowski entre distintos tipos de polígonos y hemos propuesto mejoras para su cálculo basadas en técnicas de paralelismo. Actualmente trabajamos en el problema inverso al resuelto por la suma de Minkowski, el cual se refiere a la descomposición de polígonos en suma de Minkowski. Sin embargo, este problema puede resolverse sólo con un algoritmo de complejidad exponencial. Debido a la complejidad inherente del mismo, propusimos un enfoque evolutivo para su resolución, donde incluimos la definición del problema, denominado SMINK-1. En esta presentación damos el marco formal del problema y presentamos avances alcanzados con respecto al análisis del espacio de soluciones del problema, a fin de considerar un conjunto mayor de soluciones.