Politopo convexo

En su libro Politopos convexos , Grünbaum define un politopo convexo como un conjunto convexo compacto con un número finito de puntos extremos :

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

Esto equivale a definir un politopo convexo acotado como la envoltura convexa de un conjunto finito de puntos, donde dicho conjunto finito debe contener el conjunto de puntos extremos del politopo. Esta definición se denomina representación de vértices ( representación V o descripción V ). ^{[ 1 ]} Para un politopo convexo compacto, la descripción V mínima es única y está dada por el conjunto de vértices del politopo. ^{[ 1 ]} Un politopo convexo se denomina politopo integral si todos sus vértices tienen coordenadas enteras.

Un politopo convexo puede definirse como la intersección de un número finito de semiplanos. Esta definición se denomina representación de semiplanos ( representación H o descripción H ). ^{[ 1 ]} Existen infinitas descripciones H de un politopo convexo. Sin embargo, para un politopo convexo de dimensión completa, la descripción H mínima es única y viene dada por el conjunto de semiplanos que definen las facetas . ^{[ 1 ]}

Un semiplano cerrado se puede escribir como una desigualdad lineal : ^{[ 1 ]}

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

dónde${\displaystyle n}$es la dimensión del espacio que contiene el politopo en consideración. Por lo tanto, un politopo convexo cerrado puede considerarse como el conjunto de soluciones del sistema de desigualdades lineales :

${\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}}}$

dónde${\displaystyle m}$es el número de semiplanos que definen el politopo. Esto se puede escribir de forma concisa como la desigualdad matricial :

${\displaystyle Ax\leq b}$

dónde${\displaystyle A}$es un${\displaystyle m\times n}$matriz,${\displaystyle x}$es un${\displaystyle n\times 1}$vector columna cuyas coordenadas son las variables${\displaystyle x_{1}}$a${\displaystyle x_{n}}$, y${\displaystyle b}$es un${\displaystyle m\times 1}$vector columna cuyas coordenadas son los lados derechos${\displaystyle b_{1}}$a${\displaystyle b_{m}}$de las desigualdades escalares.

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

Los coeficientes de cada fila de${\displaystyle A}$y${\displaystyle b}$Corresponden con los coeficientes de la desigualdad lineal que define el semiplano correspondiente. Por lo tanto, cada fila de la matriz corresponde a un hiperplano de soporte del politopo, un hiperplano que delimita un semiplano que contiene el politopo. Si un hiperplano de soporte también interseca al politopo, se denomina hiperplano de delimitación (ya que, al ser un hiperplano de soporte, solo puede intersecar al politopo en su frontera).

La definición anterior presupone que el politopo es de dimensión completa. En este caso, existe un conjunto mínimo único de desigualdades definitorias (salvo multiplicación por un número positivo). Las desigualdades que pertenecen a este sistema mínimo único se denominan esenciales . El conjunto de puntos de un politopo que satisfacen una desigualdad esencial con igualdad se denomina faceta .

Si el politopo no es de dimensión completa, entonces las soluciones de${\displaystyle Ax\leq b}$yacen en un subespacio afín propio de${\displaystyle \mathbb {R} ^{n}}$El politopo puede estudiarse como un objeto en este subespacio. En este caso, existen ecuaciones lineales que satisfacen todos los puntos del politopo. Añadir una de estas ecuaciones a cualquiera de las desigualdades que lo definen no altera el politopo. Por lo tanto, en general, no existe un conjunto mínimo único de desigualdades que definan el politopo.

En general, la intersección de semiplanos arbitrarios no tiene por qué estar acotada. Sin embargo, si se desea una definición equivalente a la de una envoltura convexa, entonces es necesario que la acotación sea explícita.

Las dos representaciones, en conjunto, proporcionan una forma eficiente de decidir si un vector dado está incluido en un politopo convexo dado: para demostrar que está en el politopo, basta con presentarlo como una combinación convexa de los vértices del politopo (se utiliza la descripción V); para demostrar que no está en el politopo, basta con presentar una única desigualdad definitoria que viola. ^{[ 5 ] : 256}

Un detalle sutil en la representación mediante vectores es que el número de vectores puede ser exponencial con respecto a la dimensión, por lo que la demostración de que un vector pertenece al politopo podría ser exponencialmente larga. Afortunadamente, el teorema de Carathéodory garantiza que todo vector en el politopo puede representarse mediante como máximo d + 1 vectores definitorios, donde d es la dimensión del espacio.

Para un politopo no acotado (a veces llamado poliedro), la descripción H sigue siendo válida, pero la descripción V debe extenderse. Theodore Motzkin (1936) demostró que cualquier politopo no acotado puede representarse como la suma de un politopo acotado y un cono poliédrico convexo . ^{[ 6 ]} En otras palabras, cada vector en un politopo no acotado es una suma convexa de sus vértices (sus "puntos definitorios"), más una suma cónica de los vectores euclidianos de sus aristas infinitas (sus "rayos definitorios"). Esto se conoce como el teorema de la base finita . ^{[ 3 ]}

Una cara de un politopo convexo es cualquier intersección del politopo con un semiplano tal que ninguno de los puntos interiores del politopo se encuentra en el borde del semiplano. De forma equivalente, una cara es el conjunto de puntos que dan igualdad en alguna desigualdad válida del politopo. ^{[ 5 ] : 258}

Si un politopo es d- dimensional, sus facetas son sus caras ( d - 1)-dimensionales, sus vértices son sus caras 0-dimensionales, sus aristas son sus caras 1-dimensionales y sus crestas son sus caras ( d - 2)-dimensionales.    

Dado un politopo convexo P definido por la desigualdad matricial${\displaystyle Ax\leq b}$Si cada fila de A corresponde a un hiperplano delimitador y es linealmente independiente de las demás filas, entonces cada faceta de P corresponde a exactamente una fila de A , y viceversa, siempre que se cumpla la igualdad. Cada punto de una faceta dada satisfará la igualdad lineal de la fila correspondiente en la matriz. (Puede o no satisfacer también la igualdad en otras filas). De manera similar, cada punto de una cresta satisfará la igualdad en dos de las filas de A.

En general, una cara de dimensión ( n - j ) satisface la igualdad en j filas específicas de A. Estas filas forman la base de la cara. Geométricamente hablando, esto significa que la cara es el conjunto de puntos del politopo que se encuentran en la intersección de j hiperplanos que lo delimitan.  

Las caras de un politopo convexo forman así una red euleriana denominada red de caras , donde el orden parcial se basa en la contención de conjuntos de caras. La definición de cara dada anteriormente permite considerar tanto al politopo como al conjunto vacío como caras, asegurando que cada par de caras tenga una unión y una intersección en la red de caras. El politopo completo es el único elemento máximo de la red, y el conjunto vacío, considerado como una cara de dimensión ( −1 ) (un politopo nulo ) de cada politopo, es el único elemento mínimo de la red.

Dos politopos se denominan combinatoriamente isomorfos si sus retículos de caras son isomorfos .

El grafo politópico (también grafo politópico , grafo de aristas , grafo del politopo o 1-esqueleto ) es el conjunto de vértices y aristas del politopo solamente, ignorando las caras de dimensiones superiores. Por ejemplo, un grafo poliédrico es el grafo politópico de un politopo tridimensional. Según un resultado de Whitney ^{[ 7 ],} la red de caras de un politopo tridimensional está determinada por su grafo. Lo mismo es cierto para politopos simples de dimensión arbitraria (Blind y Mani-Levitska 1987, demostrando una conjetura de Micha Perles ). ^{[ 8 ]} Kalai (1988) ^{[ 9 ]} da una demostración simple basada en orientaciones de sumideros únicas . Debido a que las redes de caras de estos politopos están determinadas por sus grafos, el problema de decidir si dos politopos tridimensionales o convexos simples son combinatoriamente isomorfos puede formularse equivalentemente como un caso especial del problema de isomorfismo de grafos . Sin embargo, también es posible trasladar estos problemas en la dirección opuesta, demostrando que la prueba de isomorfismo de politopos es completa en cuanto a isomorfismo de grafos. ^{[ 10 ]}

Un politopo convexo, como cualquier subconjunto convexo compacto de R ⁿ , es homeomorfo a una bola cerrada . ^{[ 11 ]} Sea m la dimensión del politopo. Si el politopo es de dimensión completa, entonces m = n . Por lo tanto, el politopo convexo es una variedad m -dimensional con frontera, su característica de Euler es 1 y su grupo fundamental es trivial. La frontera del politopo convexo es homeomorfa a una ( m − 1)-esfera . La característica de Euler de la frontera es 0 para m par y 2 para m impar . La frontera también puede considerarse como una teselación del espacio esférico ( m − 1)-dimensional , es decir, como un recubrimiento esférico .    

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

Dado un politopo convexo r -dimensional P , un subconjunto de sus vértices que contiene ( r +1) puntos afínmente independientes define un r -símplex . Es posible formar una colección de subconjuntos tales que la unión de los símplices correspondientes sea igual a P , y la intersección de dos símplices cualesquiera sea vacía o un símplex de menor dimensión. Esta descomposición simplicial es la base de muchos métodos para calcular el volumen de un politopo convexo, ya que el volumen de un símplex se puede obtener fácilmente mediante una fórmula. ^{[ 12 ]}

Todo poliedro convexo regular ( sólido platónico ) puede diseccionarse en un número par de instancias de su ortoesquema característico .

Las distintas representaciones de un politopo convexo tienen diferentes utilidades; por lo tanto, la construcción de una representación a partir de otra es un problema importante. El problema de la construcción de una representación V se conoce como el problema de enumeración de vértices , y el problema de la construcción de una representación H se conoce como el problema de enumeración de facetas . Si bien el conjunto de vértices de un politopo convexo acotado lo define de forma única, en diversas aplicaciones es importante conocer más sobre la estructura combinatoria del politopo, es decir, sobre su retículo de caras. Diversos algoritmos de envolvente convexa abordan tanto la enumeración de facetas como la construcción del retículo de caras.

En el caso planar, es decir, para un polígono convexo , tanto el problema de enumeración de facetas como el de enumeración de vértices se reducen a ordenar los vértices (o aristas) alrededor de la envoltura convexa. Es una tarea trivial cuando el polígono convexo se especifica de la manera tradicional para polígonos , es decir, mediante 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 se convierte en O ( m  log m ). ^{[ 13 ]} Se conoce una cota inferior correspondiente en el modelo de cálculo de árbol de decisión algebraico . ^{[ 14 ]} 

La tarea de calcular el volumen de un politopo convexo se ha estudiado en el campo de la geometría computacional . El volumen se puede calcular de forma aproximada , por ejemplo, utilizando la técnica de aproximación de volumen convexo , cuando se tiene acceso a un oráculo de pertenencia . En cuanto al cálculo exacto , un obstáculo es que, cuando se da una representación del politopo convexo como un sistema de ecuaciones de desigualdades lineales , el volumen del politopo puede tener una longitud de bits que no es polinómica en esta representación. ^{[ 15 ]}