Politopo convexo

En su libro Convex polytopes, Grünbaum define un politopo convexo como un espacio compacto convexo con un número finito de puntos extremos:

Un conjunto ${\displaystyle K}$ de ${\displaystyle \mathbb {R} ^{n}}$ es convexo si, para cada par de puntos distintos ${\displaystyle a,b\in K}$, el segmento cerrado con puntos finales a y b está totalmente contenido dentro de ${\displaystyle K}$.

Esto equivale a definir un politopo convexo acotado como la envolvente convexa de un conjunto finito de puntos, donde el conjunto finito debe contener el conjunto de puntos extremos del politopo. Dicha definición se denomina representación de vértices (representación en V o descripción en V).[1] Para un politopo convexo compacto, la descripción en V mínima es única y está dada por el conjunto de vértices del politopo.[1]

Un politopo convexo puede definirse como una intersección de un número finito de semiespacios. Dicha definición se denomina representación de semiespacios (H-representación o H-descripción).[1] Existen infinitas H-representaciones de un politopo convexo. Sin embargo, para un politopo convexo de dimensión total, la descripción H mínima es de hecho única y viene dada por el conjunto de los semiespacios que definen sus facetas.[1]

Un semiespacio puede denotarse como una desigualdad lineal:[1]

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}\leq b}$

donde n es la dimensión del espacio que contiene el politopo dado. Por lo tanto, un politopo convexo cerrado puede considerarse como el conjunto de soluciones para la desigualdad lineal:

${\displaystyle {\begin{alignedat}{7}a_{11}x_{1}&&\;+\;&&a_{12}x_{2}&&\;+\cdots +\;&&a_{1n}x_{n}&&\;\leq \;&&&b_{1}\\a_{21}x_{1}&&\;+\;&&a_{22}x_{2}&&\;+\cdots +\;&&a_{2n}x_{n}&&\;\leq \;&&&b_{2}\\\vdots \;\;\;&&&&\vdots \;\;\;&&&&\vdots \;\;\;&&&&&\;\vdots \\a_{m1}x_{1}&&\;+\;&&a_{m2}x_{2}&&\;+\cdots +\;&&a_{mn}x_{n}&&\;\leq \;&&&b_{m}\\\end{alignedat}}}$

donde m es el número de semiespacios que definen el politopo. Esto se puede escribir de forma concisa como la desigualdad matricial:

${\displaystyle Ax\leq b}$

donde A es una matriz de orden m×n, donde x es un vector columna de variables de orden n×1, y b es un vector columna de constantes de orden m×1.

Un politopo abierto convexo se define de la misma manera, utilizando en las fórmulas desigualdades estrictas en lugar de las no estrictas.

Los coeficientes de cada fila de A y b se corresponden con los coeficientes de la desigualdad lineal que define el semiespacio respectivo. Por lo tanto, cada fila en la matriz se corresponde con un hiperplano de apoyo del politopo, un hiperplano que delimita un semiespacio que contiene el politopo. Si un hiperplano de soporte también se cruza con el politopo, se denomina un "hiperplano de delimitación" (ya que es un hiperplano de soporte, solo puede intersecar el politopo en el límite del politopo).

La definición anterior asume que el politopo es de dimensión total. Si no lo es, entonces la solución de Ax ≤ b se encuentra en un espacio afín propio de Rⁿ y la discusión del politopo puede estar restringida a este subespacio.

En general, la intersección de semiespacios arbitrarios no necesita estar delimitada. Sin embargo, si se desea tener una definición equivalente a la de un casco convexo, entonces el límite debe ser considerado explícitamente.

El teorema de base finita[2] es una extensión de la noción de descripción en V para incluir politopos infinitos. El teorema establece que un poliedro convexo es la combinación convexa de sus vértices más la suma cónica de los vectores de sus bordes infinitos.

Una cara de un politopo convexo es una intersección del politopo con un semiespacio, de tal manera que ninguno de los puntos interiores del politopo se encuentra en el límite del semiespacio. Si un politopo es d dimensional, posee caras de dimensión 0, sus vértices; caras de dimensión 1, sus aristas; caras de dimensión 2, sus caras propiamente dichas; caras de dimensión 3, sus volúmenes; y así sucesivamente hasta caras de dimensión d −( -1).

Dado un politopo convexo P definido por la desigualdad de la matriz ${\displaystyle Ax\leq b}$, si cada fila de A se corresponde con un hiperplano delimitador y es independiente de las otras filas, entonces cada cara de P se corresponde exactamente con una fila de A, y viceversa. Cada punto en una faceta dada satisfará la igualdad lineal de la fila correspondiente en la matriz (y puede o no satisfacer también la igualdad en otras filas). De manera similar, cada punto de una arista satisfará la igualdad en dos de las filas de A.

La retícula facial de una pirámide cuadrada, representada mediante un Diagrama de Hasse; cada cara de la retícula está rotulada en el diagrama y cada cara figura en la retícula con el conjunto de sus vértices

En general, una cara (n − j)-dimensional satisface la igualdad en j filas específicas de A. Estas filas forman una base de la cara. Hablando geométricamente, esto significa que la cara es el conjunto de puntos en el politopo que se encuentran en la intersección de j de los hiperplanos delimitadores del politopo.

Las caras de un politopo convexo forman así un conjunto parcialmente ordenado euleriano, una retícula llamada su red de caras, donde el orden parcial se estructura mediante la relación de contenido establecida a partir de las caras. La definición de una cara dada anteriormente permite que tanto el propio politopo como el conjunto vacío sean considerados como caras, asegurando que cada par de caras tenga una unión en la retícula de caras. El politopo completo es el elemento máximo único de la celosía, y el conjunto vacío, considerado como una cara de dimensión (−1) (un politopo nulo) perteneciente a cada politopo, que es el elemento mínimo único de la celosía.

Dos politopos se denominan combinatoriamente isomórficos si sus retículas faciales son isomórficas.

El grafo del politopo (gráfo politópico o 1-esqueleto, es el conjunto de vértices y aristas del politopo exclusivamente, ignorando las caras de dimensiones superiores. Por ejemplo, un grafo poliédrico es el gráfico de un politopo tridimensional. De acuerdo con un resultado de Whitney,[3] la retícula facial de un politopo tridimensional está determinada por su gráfica. Lo mismo es cierto para los politopos simples de dimensión arbitraria (Blind & Mani-Levitska 1987, que demuestran una conjetura de Micha Perles).[4] Kalai (1988) [5] ofrece una prueba simple basada en orientaciones de sumidero únicas. Debido a que las celosías frontales de estos politopos están determinadas por sus gráficas, el problema de decidir si dos politopos convexos simples o tridimensionales son combinatoriamente isomorfos puede formularse de manera equivalente como un caso especial del problema del isomorfismo de grafos. Sin embargo, también es posible traducir estos problemas en la dirección opuesta, lo que demuestra que la prueba de isomorfismo de un politopo es la existencia de un gráfico de isomorfismo completo.[6]

Un politopo convexo, como cualquier subconjunto convexo compacto de Rⁿ, es homeomórfico para una bola cerrada.[7] Si m denota la dimensión del politopo, y el politopo es de dimensión total, entonces m = n. El politopo convexo, por lo tanto, es una variedad m dimensional con límite, su característica de Euler es 1 y su grupo fundamental es trivial. El límite del politopo convexo es homeomorfo a una (m − 1)-esfera. La característica de Euler del límite es 0 para m par y de 2 para m impar. El límite también puede considerarse como un teselado de dimensión (m − 1) sobre un espacio esférico, es decir, como un teselado esférico.

Un politopo convexo puede descomponerse en un complejo simplicial, o unión de símplex, satisfaciendo ciertas propiedades.

Dado un politopo convexo P de dimensión r, un subconjunto de sus vértices que contenga (r + 1) puntos afínmente independientes, define un r-símplex. Es posible formar una colección de subconjuntos de tal manera que la unión de los simplex correspondientes sea igual a P, y la intersección de cualquier pareja de símplex esté vacía o sea un símplex de dimensión inferior. Esta descomposición en simplex es la base de muchos métodos para calcular el volumen de un politopo convexo, ya que el volumen de un símplex se obtiene fácilmente mediante una fórmula algebraica.[8]

Las distintas representaciones de un politopo convexo tienen diferentes utilidades, por lo tanto, la construcción de una representación dada u otra es una custión importante. El problema de la construcción de una representación en V se conoce como problema de enumeración de vértices y el problema de la construcción de una representación en H se conoce como el problema de enumeración de facetas. Si bien el conjunto de vértices de un politopo convexo delimitado lo define de manera única, en varias aplicaciones es importante saber más sobre la estructura combinatoria del politopo, es decir, sobre su retícula facial. Varios algoritmos de casco convexo tratan tanto de la enumeración de facetas como de la construcción de retículas faciales.

En el caso del plano, es decir, para un polígono convexo, los problemas de enumeración de facetas y vértices equivalen a la ordenación de vértices (o aristas) alrededor del recinto convexo. Es una tarea trivial cuando el polígono convexo se especifica de forma tradicional, es decir, por la secuencia ordenada de sus vértices ${\displaystyle v_{1},\dots ,v_{m}}$. Cuando la lista de entrada de vértices (o aristas) no está ordenada, la complejidad temporal de los problemas alcanza el grado O(m log m). Un mayorante coincidente se conoce en el modelo de cálculo como árbol de decisión algebraico.[9]