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 real afín (o euclidiano ) de cualquier dimensión n , que tiene lados planos. También se puede definir 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 se denomina politopo . ^[1]^[2]

Analíticamente, un poliedro convexo se expresa como el conjunto de soluciones 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 los problemas de programación lineal . ^[3]^{: 9}

Ejemplos

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

Un semiespacio 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 ₁ (que es equivalente a -a ₁^Tx ≤ - b ₁ ).
Un cuadrante en el plano. Por ejemplo, la región del plano cartesiano que consta de todos los puntos 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 3-espacial, ${ (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 de 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$ está acotada (por lo tanto, es 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 está acotada.

Caras y vértices

Un subconjunto F de un poliedro P se denomina cara de P si existe un semiespacio H (definido por alguna desigualdad a ₁^Tx ≤ b ₁ ) tal que H contiene a P y F es la intersección de H y P . ^[3]^{: 9}

Si una cara contiene un solo punto { v }, entonces v se llama vértice de P .
Si una cara F no está vacía y tiene una 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 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 inecuaciones lineales no es única. Es habitual 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 para todo i . $\|a_{i}\|_{\infty }=1$
Si P no es de dimensión completa, entonces está contenido en su envoltura afín , que está definida por un conjunto de ecuaciones lineales C x = d . Es posible elegir C de modo 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 modo que para todo i , y cada a _i es ortogonal a cada fila de C. Esta representación es única hasta la elección de las columnas de la matriz identidad. $\|a_{i}\|_{\infty }=1$

Representación mediante conos y envolturas convexas

Si P es un politopo (un poliedro acotado), entonces puede representarse por 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 ilimitado), entonces puede representarse 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 de P puede escribirse como una combinación convexa de, como máximo, d +1 vértices afínmente independientes de P. El teorema puede generalizarse: si P es cualquier poliedro d -dimensional, entonces cada punto de 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 determinado poliedro se puede representar mediante una codificación con un número pequeño de bits. Existen varias medidas de la complejidad de representación de un poliedro P : ^[3]^{: 163}

P tiene una complejidad de facetas de f como máximo , si P 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, ya que hay n+1 coeficientes en cada desigualdad.
P tiene una complejidad de vértice 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 , ya 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 como máximo f , entonces P tiene una complejidad de vértice como máximo 4 n ² f .
Si P tiene una complejidad de vértice como máximo v , entonces P tiene una complejidad de faceta 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 (un límite superior de la complejidad de las facetas). Esto es equivalente a exigir que conozcamos n y v (un límite superior de la complejidad de los vértices).

En algunos casos, conocemos un límite superior para la complejidad de las facetas de un poliedro P , pero no conocemos las desigualdades específicas que alcanzan este límite superior. 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 superior e inferior en el volumen de P : ^[3]^{: 165}

Si P tiene una complejidad de vértice como máximo v , entonces, trivialmente, todos los vértices de P están contenidos en la bola de radio 2 ^v 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 una complejidad de facetas de f como máximo , entonces P contiene una bola de radio . Además, esta bola está contenida en la bola de radio que rodea el origen. $Estilo de visualización 2-7n3f$ $Estilo de visualización 2^{5n^{2}f}$

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

Si P es un poliedro con complejidad de facetas como máximo f , e y es un vector racional cuyas entradas tienen 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értice 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 desde P de como máximo 2 ^{-6n f} , 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 se pueden encontrar en politiempo usando aproximación diofántica simultánea . $\|qv-w\|<2^{-3f},0<q<2^{4nf}$
Si P es un poliedro con complejidad de vértice como máximo v , y P satisface la desigualdad a ^Tx ≤ b + 2 ^-6nv , y q,c,d son vectores enteros que satisfacen , entonces P satisface la desigualdad c ^Tx ≤ d . Los números q,d y el vector c se pueden encontrar en politiempo usando aproximación diofántica simultánea . $\|qa-c\|+|qb-d|<2^{-3v},0<q<2^{4nv}$

Véase también

Problemas algorítmicos sobre conjuntos convexos

Referencias

^ Grünbaum, Branko (2003), Politopos convexos , Textos de posgrado 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, Sr. 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, Sr. 2508056.
^ abcdefghijk 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, Sr. 1261419