poliedro N- dimensional

Un poliedro n -dimensional 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 afín (o euclidiano ) real de cualquier dimensión n , con lados planos. Alternativamente, puede definirse como la intersección de un número finito de semiplanos . A diferencia de un poliedro tridimensional, puede ser acotado o no acotado. En esta terminología, un poliedro acotado se denomina politopo . ^[¹^]^[²^]

Analíticamente, un poliedro convexo se expresa como el conjunto solución de un sistema de desigualdades lineales, a _i^Tx ≤ b _i , donde a _i son vectores en R ⁿ y b _i son escalares. Esta definición de poliedros es particularmente importante ya que proporciona una perspectiva geométrica para problemas de programación lineal . ^{[ 3 ]}^{: 9}

Ejemplos

Muchas formas poliédricas tradicionales son poliedros n-dimensionales. Otros ejemplos incluyen:

Un semiplano es un poliedro definido por una única desigualdad lineal, a ₁^Tx ≤ b ₁ .
Un hiperplano es un poliedro definido por dos desigualdades, a ₁^Tx ≤ b ₁ y a ₁^Tx ≥ b ₁ (lo que es equivalente a -a ₁^Tx ≤ - b ₁ ).
Un cuadrante en el plano. Por ejemplo, la región del plano cartesiano que comprende todos los puntos situados por encima del eje horizontal y a la derecha del eje vertical: ${ (x, y) : x \geq 0, y \geq 0$ }. Sus lados son los dos ejes positivos y, por lo demás, no tiene límites.
Un octante en el espacio euclidiano tridimensional, ${ (x, y, z) : x \geq 0, y \geq 0, z \geq 0$ }.
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 : ${ (x, y, z) : 0 \leq x \leq 1, 0 \leq y \leq 1$ }.
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 $c \in S$ es acotada (por lo tanto, un poliedro tradicional) cuando c se encuentra en el interior de la envoltura convexa de S , y en caso contrario (cuando c se encuentra en el límite de la envoltura convexa de S ) A no es acotada.

Caras y vértices

Un subconjunto no vacío F de un poliedro P se llama cara de P si F=P o si existe un semiplano H (definido por alguna desigualdad a ₁^Tx ≤ b ₁ ) tal que H contiene ^a P y F es la intersección del límite de H y P. ^[⁴ ]

Si una cara contiene un único punto { v } , entonces v se denomina vértice de P.
Si una cara F es n -1 dimensional, entonces F se llama una faceta de P.

Supongamos que P es un poliedro definido por Ax ≤ b , donde A tiene rango de columna completo. Entonces, v es un vértice de P si y solo si v es una solución factible básica del sistema lineal Ax ≤ b . ^{[ 3 ]}^{: 10}

Representación estándar

La representación de un poliedro mediante un conjunto de desigualdades lineales no es única. Es común definir una representación estándar para cada poliedro P : ^{[ 3 ]}^{: 9}

Si P es de dimensión completa, entonces su representación estándar es un conjunto de desigualdades tales que cada desigualdad a _i^Tx ≤ b _i define exactamente una faceta de P , y además, las desigualdades están normalizadas de tal manera que $\|a_{i}\|_{\infty }=1$ para todos yo .
Si P no es de dimensión completa, entonces está contenido en su envoltura afín , que se define mediante un conjunto de ecuaciones lineales C x= d . Es posible elegir C de tal manera que C = ( I , C'), donde I es una matriz identidad . La representación estándar de P contiene este conjunto C x= d y un conjunto de desigualdades tales que cada desigualdad a _i^Tx ≤ b _i define exactamente una faceta de P , las desigualdades están normalizadas de tal manera que $\|a_{i}\|_{\infty }=1$ para todo i , y cada a _i 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 envoltura convexa de V : P = conv( V ).

Si P es un poliedro general (posiblemente no acotado), entonces se puede representar como: P = conv(V) + cone(E), donde V es (como antes) el conjunto de vértices de P , y E es otro conjunto finito, y cone denota la envoltura cónica . El conjunto cone(E) también se denomina cono de recesión de P. ^{[ 3 ]}^{: 10}

El teorema de Carathéodory establece que, si P es un politopo d- dimensional, entonces cada punto en P puede escribirse como una combinación convexa de a lo sumo d + 1 vértices afínmente independientes de P. El teorema puede generalizarse: si P es cualquier poliedro d -dimensional, entonces cada punto en P puede escribirse como una combinación convexa de puntos v ₁ ,..., v _s , v ₁ + e ₁ ,..., v ₁ + e _t con s + t ≤ d + 1, tales que v ₁ ,..., v _s son elementos de las caras mínimas no vacías de P y e ₁ ,..., e _t son elementos de las caras mínimas no nulas del cono de recesión de P. ^{[ 3 ]}^{: 10}

Complejidad de la representación

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

P tiene una complejidad de facetas de como máximo f si puede representarse mediante un sistema de desigualdades lineales con coeficientes racionales, de modo 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 como máximo f . Nótese que f ≥ n + 1, puesto que hay n + 1 coeficientes en cada desigualdad.
P tiene una complejidad de vértices como máximo v , si P puede representarse como conv( V )+cone( E ), donde V y E son conjuntos finitos, de modo que cada punto en V o E tiene una longitud de codificación como máximo v . Nótese que v ≥ n , puesto que hay n coeficientes en cada vector.

Estos dos tipos de complejidad están estrechamente relacionados: ^{[ 3 ]}^{: Lem.6.2.4}

Si P tiene una complejidad de facetas de como máximo f , entonces P tiene una complejidad de vértices de como máximo 4 n ²f .
Si P tiene una complejidad de vértices como máximo v , entonces P tiene una complejidad de facetas como máximo 3 n ²v .

Se dice que un poliedro P está bien descrito si conocemos n (el número de dimensiones) y f (una cota superior para la complejidad de las facetas). Esto equivale a requerir que conozcamos n y v (una cota superior para la complejidad de los vértices).

En algunos casos, conocemos una cota superior para la complejidad de facetas de un poliedro P , pero desconocemos las desigualdades específicas que alcanzan dicha cota. Sin embargo, se puede demostrar que la longitud de codificación en cualquier representación estándar de P es como máximo 35 n ²f . ^{[ 3 ]}^{: Lem.6.2.3}

La complejidad de la representación de P implica límites superiores e inferiores en el volumen de P : ^{[ 3 ]}^{: 165}

Si P tiene una complejidad de vértices de como máximo v , entonces, trivialmente, todos los vértices de P están contenidos en la bola de radio 2v ^alrededor del origen. Esto significa que, si P es un politopo, entonces P mismo está circunscrito en esa bola.
Si P es un poliedro de dimensión completa con complejidad de facetas como máximo f , entonces P contiene una bola con radio $2^{-7n^{3}f}$ . Además, esta bola está contenida en la bola de radio $2^{5n^{2}f}$ alrededor del origen.

Una pequeña complejidad de representación es útil para "redondear" soluciones aproximadas a soluciones exactas. Específicamente: ^{[ 3 ]}^{: 166}

Si P es un poliedro con complejidad de facetas como máximo f , e y es un vector racional cuyas entradas tienen un denominador común como máximo q , y la distancia de y a P es como máximo 2 ^{-2 f} / q , entonces y está de hecho en P.
Si P es un poliedro con complejidad de vértices como máximo v , y P satisface la desigualdad a ^Tx ≤ b + 2 ^-v-1 , entonces P también satisface la desigualdad a ^Tx ≤ b.
Si P es un poliedro con complejidad de facetas como máximo f , y v es un vector racional con distancia de P de como máximo 2 ^{-6n f} , y q y w son vectores enteros que satisfacen $\|qv-w\|<2^{-3f},0<q<2^{4nf}$ , entonces el punto w / q está contenido en P . El número q y el vector w se pueden encontrar en tiempo polinomial usando aproximación diofántica simultánea .
Si P es un poliedro con complejidad de vértices como máximo v , y P satisface la desigualdad a ^Tx ≤ b + 2 ^-6nv , y q,c,d son vectores enteros que satisfacen $\|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}$ , entonces P satisface la desigualdad c ^Tx ≤ d . Los números q,d y el vector c se pueden encontrar en tiempo polinomial usando aproximación diofántica simultánea .

Véase también

Problemas algorítmicos sobre conjuntos convexos

Referencias

↑ Grünbaum, Branko (2003), Politopos convexos , Textos de Licenciatura en Matemáticas, vol. 221 (2ª ed.), Nueva York: Springer-Verlag, pág. 26, doi : 10.1007/978-1-4613-0019-9 , ISBN 978-0-387-00424-2, MR 1976856 .
↑ Bruns, Winfried; Gubeladze, Joseph (2009), "Definición 1.1" , Politopos, anillos y teoría K , Monografías de Springer en Matemáticas, Dordrecht: Springer, p. 5, CiteSeerX 10.1.1.693.2630 , doi : 10.1007/b105283 , ISBN 978-0-387-76355-2, MR 2508056 .
1 2 3 4 5 6 7 8 9 10 Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419
↑ Brenner, Ulrich (14 de julio de 2022). "Optimización lineal y entera (V3C1/F4C1)" (PDF) . Instituto de Investigación de Matemáticas Discretas, Universidad de Bonn . Recuperado el 19 de octubre de 2025 .

[polytope-bounded-12-1] Grünbaum, Branko (2003), Politopos convexos , Textos de Licenciatura en Matemáticas, vol. 221 (2ª ed.), Nueva York: Springer-Verlag, pág. 26, doi : 10.1007/978-1-4613-0019-9 , ISBN 978-0-387-00424-2, MR 1976856 .

[polytope-bounded-22-2] Bruns, Winfried; Gubeladze, Joseph (2009), "Definición 1.1" , Politopos, anillos y teoría K , Monografías de Springer en Matemáticas, Dordrecht: Springer, p. 5, CiteSeerX 10.1.1.693.2630 , doi : 10.1007/b105283 , ISBN 978-0-387-76355-2, MR 2508056 .

[:02-3] 1 2 3 4 5 6 7 8 9 10 Grötschel, Martín ; Lovász, László ; Schrijver, Alexander (1993), Algoritmos geométricos y optimización combinatoria , Algoritmos y combinatoria, vol. 2 (2ª ed.), Springer-Verlag, Berlín, doi : 10.1007/978-3-642-78240-4 , ISBN 978-3-642-78242-8, MR 1261419

[4] Brenner, Ulrich (14 de julio de 2022). "Optimización lineal y entera (V3C1/F4C1)" (PDF) . Instituto de Investigación de Matemáticas Discretas, Universidad de Bonn . Recuperado el 19 de octubre de 2025 .

[

[

a