En matemáticas, el problema de enumeración de vértices para un politopo , un complejo de células poliédricas , una disposición de hiperplano o algún otro objeto de geometría discreta , es el problema de la 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 de m × n , x es un vector de variables de columna de n × 1 y b es un vector de constantes de columna de m × 1.
Complejidad computacional
La complejidad computacional del problema es un tema de investigación en informática . Para poliedros ilimitados, se sabe que el problema es NP-duro, más precisamente, no existe un algoritmo que se ejecute en tiempo polinomial en el tamaño de entrada-salida combinado, a menos que P = NP. [2]
Un artículo de 1992 de David Avis y Komei Fukuda [3] presenta un algoritmo que encuentra los v vértices de un politopo definido por un sistema no degenerado de n desigualdades en d dimensiones (o, doblemente, las v facetas del casco convexo de n puntos d dimensiones, donde cada faceta contiene exactamente d puntos dados) en el tiempo O ( ndv ) y el espacio O ( nd ). Los v vértices en una disposición simple de n hiperplanos en d dimensiones se pueden encontrar en O ( n 2 dv ) tiempo y O ( nd ) complejidad espacial. El algoritmo Avis-Fukuda adaptó el algoritmo entrecruzado para matroides orientados.
Notas
- ^ Eric W. Weisstein CRC Concise Encyclopedia of Mathematics, 2002, ISBN 1-58488-347-2 , p. 3154, artículo "enumeración de vértices"
- ^ Leonid Khachiyan; Endre Boros; Konrad Borys; Khaled Elbassioni; Vladimir Gurvich (marzo de 2008). "Generar todos los vértices de un poliedro es difícil" . Geometría discreta y computacional . 39 (1-3): 174-190. doi : 10.1007 / s00454-008-9050-5 .
- ^ David Avis; Komei Fukuda (diciembre de 1992). "Un algoritmo pivotante para cascos convexos y enumeración de vértices de arreglos y poliedros" . Geometría discreta y computacional . 8 (1): 295–313. doi : 10.1007 / BF02293050 .
Referencias
- Avis, David ; Fukuda, Komei (diciembre de 1992). "Un algoritmo pivotante para cascos convexos y enumeración de vértices de arreglos y poliedros" . Geometría discreta y computacional . 8 (1): 295–313. doi : 10.1007 / BF02293050 . Señor 1174359 .