+ Ejemplos de poliedros de dimensión 3 y de dimensión 4Cubo (3-cubo)Teseracto (4-cubo)

Un poliedro n dimensional (o también poliedro n-dimensional o poliedro de dimensión n) es un objeto geométrico que generaliza el poliedro tridimensional a un espacio n dimensional. Se define como un conjunto de puntos en un espacio real afín (o espacio euclídeo) de cualquier dimensión n que posee caras planas. Alternativamente, puede definirse como la intersección de un número finito de semiespacios. A diferencia de un poliedro tridimensional, puede ser acotado o no acotado. En esta terminología, un poliedro acotado recibe el nombre de politopo...

Analíticamente, un poliedro convexo se expresa como el conjunto de soluciones de un sistema de desigualdades lineales, ai T x ≤ bi, donde ai son vectores en Rn y bi son escalares. Esta definición de poliedro es particularmente importante, ya que proporciona una perspectiva geométrica para problemas en programación lineal. Grötschel, Martin; Lovász, László; Schrijver, Alexander (1993), Geometric algorithms and combinatorial optimization, Algorithms and Combinatorics, vol. 2 (2nd ed.), Springer-Verlag, Berlin, doi:10.1007/978-3-642-78240-4, ISBN 978-3-642-78242-8, MR 1261419

Ejemplos Muchas formas poliédricas tradicionales son poliedros de n dimensiones. Otros ejemplos incluyen:

Un semiespacio es un poliedro definido por una única desigualdad lineal, a1 T x ≤ b1. Un hiperplano es un poliedro definido por dos desigualdades, a1Tx ≤ b1 y a1Tx ≥ b1 (lo cual es equivalente a -a1Tx ≤ -b1). Un cuadrante en el plano. Por ejemplo, la región del plano cartesiano que consta de todos los puntos situados por encima del eje horizontal y a la derecha del eje vertical: }. Sus lados son los dos ejes positivos y, por lo demás, es no acotado. Un octante en el espacio euclidiano tridimensional, }. Un prisma de extensión infinita. Por ejemplo, un prisma cuadrado doblemente infinito en el espacio tridimensional, que consiste en un cuadrado en el plano xy barrido a lo largo del eje z: }. Cada celda en una teselación de Voronoi es un poliedro. En la teselación de Voronoi de un conjunto S, la celda A correspondiente a un punto está acotada (y por tanto es un poliedro tradicional) cuando c se encuentra en el interior de la envolvente convexa de S; en caso contrario (cuando c se encuentra en el boundary de la envolvente convexa de S), A es no acotada.

Caras y vértices Un subconjunto no vacío F de un poliedro P se denomina cara de P si F=P o si existe un semiespacio H (definido por una desigualdad a1Tx ≤ b1) tal que H contiene a P y F es la intersección de la frontera de H y P.

Si una cara consta de un único punto {v}, entonces v se denomina vértice de P. Si una cara F tiene dimensión n-1, entonces F se denomina faceta de P. Supóngase que P es un poliedro definido por Ax ≤ b, donde A tiene rango completo por columnas. Entonces, v es un vértice de P si y solo si v es una solución básica factible del sistema lineal Ax ≤ b.

Representación estándar La representación de un poliedro mediante un conjunto de desigualdades lineales no es única. Es habitual definir una representación estándar para cada poliedro P:

Si P es de dimensión completa, entonces su representación estándar es un conjunto de desigualdades tal que cada desigualdad aiTx ≤ bi define exactamente una faceta de P; además, las desigualdades están normalizadas de modo que para todo i. Si P no es de dimensión completa, entonces está contenido en su envolvente afín, que se define mediante un conjunto de ecuaciones lineales Cx=d. Es posible elegir C de tal manera que C = (I, C´), donde I es la matriz identidad. La representación estándar de P incluye este conjunto Cx=d y un conjunto de desigualdades tal que cada desigualdad aiTx ≤ bi define exactamente una faceta de P, las desigualdades están normalizadas de modo que para todo i, y cada ai es ortogonal a cada fila de C. Esta representación es única salvo por la elección de las columnas de la matriz identidad.

Representación mediante conos y envolventes convexas Si P es un politopo (un poliedro acotado), entonces puede representarse mediante su conjunto de vértices V, ya que P es simplemente la envolvente convexa de V: P = conv(V).

Si P es un poliedro general (que puede ser no acotado), entonces puede representarse como: P = conv(V) + cone(E), donde V es (como antes) el conjunto de vértices de P, E es otro conjunto finito y cone denota la combinación cónica. El conjunto cone(E) también se denomina cono de recesión de P.

El teorema de Carathéodory establece que, si P es un politopo de dimensión d, entonces cualquier punto de P puede expresarse como una combinación convexa de, a lo sumo, d+1 vértices de P afínmente independientes. El teorema puede generalizarse: si P es un poliedro cualquiera de dimensión d, entonces cualquier punto de P puede expresarse como una combinación convexa de puntos v1,...,vs, v1+e1,...,v1+et con s+t ≤ d+1, tales que v1,...,vs son elementos de las caras no vacías minimales de P y e1,...,et son elementos de las caras no nulas minimales del cono de recesión de P.

Complejidad de la representación Al resolver problemas algorítmicos sobre poliedros, es importante saber si un determinado poliedro puede representarse mediante una codificación con un número reducido de bits. Existen varias medidas para la complejidad de la representación de un poliedro P:

P tiene una complejidad de facetas de a lo sumo f, si P puede representarse mediante un sistema de desigualdades lineales con coeficientes racionales, de tal manera que la longitud de codificación de cada desigualdad (es decir, la longitud de codificación binaria de todos los números racionales que aparecen como coeficientes en la desigualdad) sea de a lo sumo f. Nótese que f ≥ n+1, dado que hay n+1 coeficientes en cada desigualdad. P tiene una complejidad de vértices de a lo sumo v, si P puede representarse como conv(V)+cone(E), donde V y E son conjuntos finitos, tales que cada punto en V o E tiene una longitud de codificación de a lo sumo v. Nótese que v ≥ n, dado que hay n coeficientes en cada vector. Estos dos tipos de complejidad están estrechamente relacionados:

Si P tiene una complejidad de facetas de a lo sumo f, entonces P tiene una complejidad de vértices de a lo sumo 4 n2 f. Si P tiene una complejidad de vértices de a lo sumo v, entonces P tiene una complejidad de facetas de a lo sumo 3 n2 v.

Un poliedro P se denomina bien descrito si se conocen n (el número de dimensiones) y f (una cota superior de la complejidad de las facetas). Esto equivale a requerir que se conozcan n y v (una cota superior de la complejidad de los vértices).

En algunos casos, se conoce una cota superior de la complejidad de las facetas de un poliedro P, pero no se conocen las desigualdades específicas que alcanzan dicha cota. No obstante, puede demostrarse que la longitud de codificación en cualquier representación estándar de P es, como máximo, 35 n2 f.

La complejidad de la representación de P implica cotas superiores e inferiores para el volumen de P:

Si P tiene una complejidad de vértices de a lo sumo v, entonces, trivialmente, todos los vértices de P están contenidos en la bola de radio 2v centrada en el origen. Esto significa que, si P es un politopo, entonces el propio P está circunscrito en dicha bola. Si P es un poliedro de dimensión completa con una complejidad de facetas de a lo sumo f, entonces P contiene una bola de radio . Además, esta bola está contenida en la bola de radio centrada en el origen. Una complejidad de representación baja resulta útil para "redondear" soluciones aproximadas y convertirlas en soluciones exactas. Específicamente: Si P es un poliedro con una complejidad de facetas de a lo sumo f, y es un vector racional cuyas componentes tienen un denominador común de a lo sumo q, y la distancia de y a P es de a lo sumo 2-2f/q, entonces y pertenece de hecho a P. Si P es un poliedro con una complejidad de vértices de a lo sumo v, y P satisface la desigualdad aTx ≤ b + 2-v-1, entonces P también satisface la desigualdad aTx ≤ b. Si P es un poliedro con una complejidad de facetas de a lo sumo f, v es un vector racional cuya distancia a P es de a lo sumo 2-6nf, y q y w son vectores enteros que satisfacen , entonces el punto w/q está contenido en P. El número q y el vector w pueden hallarse en tiempo polinómico utilizando una aproximación diofántica. Si P es un poliedro con complejidad de vértices a lo sumo v, y P satisface la desigualdad aTx ≤ b + 2-6nv, y q, c, d son vectores enteros que satisfacen , entonces P satisface la desigualdad cTx ≤ d. Los números q, d y el vector c pueden hallarse en tiempo polinómico utilizando una aproximación diofántica.

Véase también Problemas algorítmicos sobre conjuntos convexos

Referencias

Categoría:Poliedros Categoría:Programación lineal