Estudio de la aplicabilidad de un enfoque evolutivo para la descomposición en Suma de Minkowski.

Abstract

Dados dos conjuntos P y Q Ì R2 la suma de Minkowski de P y Q, denotada por P Å Q se define como P Å Q = {p + q : p Î P, q ÎQ } donde p+q es el vector suma de los vectores p y q. El problema que nos planteamos es el problema inverso al resuelto por la suma de Minkowski. Dado un polígono S, ¿existen polígonos P y Q tales que S es la suma de Minkowski de P y Q, es decir, S = P Å Q? Este problema se puede resolver con un algoritmo de complejidad exponencial. Debido a la complejidad inherente de este problema, se propone un enfoque evolutivo para su resolución. La propuesta incluye la definición del problema en términos de una función objetivo, el diseño e implementación de un algoritmo genético y su aplicación a un conjunto de instancias del problema.