Aproximación de volumen convexo
En el análisis de algoritmos , varios autores han estudiado el cálculo del volumen de cuerpos convexos de alta dimensión , un problema que también se puede utilizar para modelar muchos otros problemas de enumeración combinatoria . A menudo, estos trabajos utilizan un modelo de cálculo de caja negra en el que la entrada la proporciona una subrutina para probar si un punto está dentro o fuera del cuerpo convexo, en lugar de una lista explícita de los vértices o caras de un politopo convexo . Se sabe que, en este modelo, ningún algoritmo determinista puede lograr una aproximación precisa, [1] [2] e incluso para una lista explícita de caras o vértices el problema es#P-difícil . [3] Sin embargo, un trabajo conjunto de Martin Dyer , Alan M. Frieze y Ravindran Kannan proporcionó un esquema de aproximación de tiempo polinómico aleatorio para el problema, proporcionando un marcado contraste entre las capacidades de los algoritmos aleatorios y deterministas. [4]
El resultado principal del artículo es un algoritmo aleatorio para encontrar una aproximación al volumen de un cuerpo convexo en el espacio euclidiano bidimensional asumiendo la existencia de un oráculo de membresía . El algoritmo toma tiempo acotado por un polinomio en , la dimensión de y . El algoritmo combina dos ideas:
El cuerpo convexo dado se puede aproximar mediante una secuencia de cuerpos anidados, llegando eventualmente a uno de volumen conocido (una hiperesfera), con este enfoque utilizado para estimar el factor por el cual el volumen cambia en cada paso de esta secuencia. Multiplicando estos factores se obtiene el volumen aproximado del cuerpo original.
Aunque el tiempo de este algoritmo es polinomial, tiene un alto exponente. Los autores posteriores mejoraron el tiempo de ejecución de este método al proporcionar cadenas de Markov de mezcla más rápida para el mismo problema. [6] [7] [8] [9]
El resultado de la aproximabilidad del tiempo polinomial se ha generalizado a estructuras más complejas, como la unión y la intersección de objetos. [10] Esto se relaciona con el problema de la medida de Klee .