En matemáticas, el problema de enumeración de vértices de un politopo , un complejo de celdas poliédricas , una disposición de hiperplanos o algún otro objeto de geometría discreta , es el problema de determinación de los vértices del objeto dada alguna representación formal del objeto. Un ejemplo clásico es el problema de enumeración de los vértices de un politopo convexo especificado por un conjunto de desigualdades lineales : [1]
donde A es una matriz m × n , x es un vector columna n × 1 de variables y b es un vector columna m × 1 de constantes. El problema inverso ( dual ) de encontrar las desigualdades limitantes dados los vértices se llama enumeración de facetas (ver algoritmos de envoltura convexa ).
La complejidad computacional del problema es un tema de investigación en informática . Para poliedros ilimitados, se sabe que el problema es NP-hard, más precisamente, no hay ningún algoritmo que se ejecute en tiempo polinomial en el tamaño combinado de entrada-salida, a menos que P=NP. [2]
Un artículo de 1992 de David Avis y Komei Fukuda [3] presenta un algoritmo de búsqueda inversa que encuentra los v vértices de un politopo definido por un sistema no degenerado de n desigualdades en d dimensiones (o, dualmente, las v facetas de la envoltura convexa de n puntos en d dimensiones, donde cada faceta contiene exactamente d puntos dados) en tiempo O ( ndv ) y espacio O( nd ). Los v vértices en una disposición simple de n hiperplanos en d dimensiones se pueden encontrar en tiempo O( n 2 dv ) y complejidad espacial O( nd ). El algoritmo de Avis-Fukuda adaptó el algoritmo criss-cross para matroides orientadas.
