Politopo convexo

Un politopo convexo es un caso especial de politopo, que tiene la propiedad adicional de que también es un conjunto convexo de puntos en un espacio $n$ -dimensional $\mathbb {R} ^{n}$ .^[1] Algunos autores usan los términos "politopo convexo" y "poliedro convexo" de manera intercambiable, mientras que otros prefieren hacer una distinción entre las nociones de poliedro y de politopo.

Además, algunos textos requieren que un politopo sea un conjunto acotado, mientras que otros^[2] (incluido este artículo) permiten que los politopos no tengan límites. Los términos "politopo convexo acotado/no acotado" se usarán a continuación cuando el límite sea crítico para el problema tratado. Sin embargo, otros textos tratan un n-politopo convexo como una superficie o una (n-1)-variedad.

Los politopos convexos desempeñan un papel importante tanto en varias ramas de las matemáticas como en ciencias aplicadas, especialmente en programación lineal.

Un libro completo e influyente sobre el tema, llamado Convex Polytopes, fue publicado en 1967 por Branko Grünbaum. En 2003 se publicó la segunda edición del libro, con un importante material adicional aportado por los nuevos redactores.^[1]

En el libro de Grünbaum, y en algunos otros textos sobre geometría discreta, los politopos convexos a menudo se llaman simplemente "politopos". Grünbaum señala que esto es solo para evitar la repetición interminable de la palabra "convexo", y que la discusión debe entenderse como aplicable solo a la variedad convexa.

Un politopo se llama de dimensión total si es un objeto $n$ dimensional en Rⁿ.

Ejemplos

Numerosos ejemplos de politopos convexos acotados se pueden encontrar en el artículo poliedro.
En el caso bidimensional, ejemplos de politopos de dimensión completa son: un semiespacio, una franja entre dos líneas paralelas, una forma de ángulo (la intersección de dos semiplanos no paralelos), una forma definida por una cadena poligonal convexa con dos rayos conectados a sus extremos, y un polígono convexo.
Los casos especiales de un politopo convexo no acotado son una franja definida entre dos hiperplanos paralelos, una cuña definida por dos semiespacios no paralelos, un cilindro (o prisma infinito) y un cono poliédrico (cono infinito) definido por tres o más semiespacios que pasan por un punto común.

Definiciones

Un politopo convexo se puede definir de varias maneras, dependiendo de lo que sea más adecuado para el problema en cuestión. La definición de Grünbaum es en términos de un conjunto convexo de puntos en el espacio. Otras definiciones importantes son: como la intersección de semiespacios (representación de semiespacios) y como la envolvente convexa de un conjunto de puntos (representación de vértices).

Representación de vértices (casco 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

K

de

\mathbb {R} ^{n}

es convexo si, para cada par de puntos distintos

a,b\in K

, el segmento cerrado con puntos finales a y b está totalmente contenido dentro de

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]

Intersección de semiespacios

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]

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:

{\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:

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.

Teorema de base finita

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.

Propiedades

Cada politopo convexo (acotado) es la imagen de un símplex, ya que cada punto es una combinación convexa de los vértices (de forma más precisa, de un número finito de vértices). Sin embargo, los politopos no son en general isomorfos a los símplex. Esto contrasta con el caso de los espacios vectoriales y las combinaciones lineales, ya que cada espacio vectorial de dimensión finita no es solo una imagen, sino que de hecho es isomorfo, con un espacio euclidiano de alguna dimensión (o análogo a otros campos).

Retícula facial

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 $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.

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]

Propiedades topológicas

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.

Descomposición en simplex

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]

Problemas algorítmicos para un politopo convexo

Construcción de representaciones

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 $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]

Referencias

↑ ^a ^b ^c ^d ^e ^f ^g Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter Matias Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466pp.
↑ ^a ^b Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0-8247-7478-7, p. 68
↑ Whitney, Hassler (1932). «Congruent graphs and the connectivity of graphs». Amer. J. Math. 54 (1): 150-168. JSTOR 2371086. doi:10.2307/2371086.
↑ Blind, Roswitha; Mani-Levitska, Peter (1987), «Puzzles and polytope isomorphisms», Aequationes Mathematicae 34 (2-3): 287-297, MR 921106, doi:10.1007/BF01830678 ..
↑ Kalai, Gil (1988), «A simple way to tell a simple polytope from its graph», Journal of Combinatorial Theory, Ser. A 49 (2): 381-383, MR 964396, doi:10.1016/0097-3165(88)90064-7 ..
↑ Kaibel, Volker; Schwartz, Alexander (2003). «On the Complexity of Polytope Isomorphism Problems». Graphs and Combinatorics 19 (2): 215-230. arXiv:math/0106093. doi:10.1007/s00373-002-0503-y. Archivado desde el original el 21 de julio de 2015.
↑ Glen E. Bredon, Topology and Geometry, 1993, ISBN 0-387-97926-3, p. 56.
↑ Büeler, B.; Enge, A.; Fukuda, K. (2000). «Exact Volume Computation for Polytopes: A Practical Study». Polytopes — Combinatorics and Computation. p. 131. ISBN 978-3-7643-6351-2. doi:10.1007/978-3-0348-8438-9_6.
↑ Yao, Andrew Chi Chih (1981), «A lower bound to finding convex hulls», Journal of the ACM 28 (4): 780-787, MR 677089, doi:10.1145/322276.322289 .; Ben-Or, Michael (1983), «Lower Bounds for Algebraic Computation Trees», Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80-86, doi:10.1145/800061.808735 ..

Enlaces externos

Wikimedia Commons alberga una categoría multimedia sobre Politopo convexo.
Weisstein, Eric W. «Convex polygon». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Weisstein, Eric W. «Convex polyhedron». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research.
Komei Fukuda, Preguntas frecuentes sobre cómputo poliédrico.

Datos: Q4129097
Multimedia: Convex polytopes / Q4129097

[grun-1] ↑ ^a ^b ^c ^d ^e ^f ^g Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter Matias Ziegler, 2003, ISBN 0-387-40409-0, ISBN 978-0-387-40409-7, 466pp.

[Jeter-2] Mathematical Programming, by Melvyn W. Jeter (1986) ISBN 0-8247-7478-7, p. 68

[3] Whitney, Hassler (1932). «Congruent graphs and the connectivity of graphs». Amer. J. Math. 54 (1): 150-168. JSTOR 2371086. doi:10.2307/2371086.

[4] Blind, Roswitha; Mani-Levitska, Peter (1987), «Puzzles and polytope isomorphisms», Aequationes Mathematicae 34 (2-3): 287-297, MR 921106, doi:10.1007/BF01830678 ..

[5] Kalai, Gil (1988), «A simple way to tell a simple polytope from its graph», Journal of Combinatorial Theory, Ser. A 49 (2): 381-383, MR 964396, doi:10.1016/0097-3165(88)90064-7 ..

[6] Kaibel, Volker; Schwartz, Alexander (2003). «On the Complexity of Polytope Isomorphism Problems». Graphs and Combinatorics 19 (2): 215-230. arXiv:math/0106093. doi:10.1007/s00373-002-0503-y. Archivado desde el original el 21 de julio de 2015.

[bredon-7] Glen E. Bredon, Topology and Geometry, 1993, ISBN 0-387-97926-3, p. 56.

[8] Büeler, B.; Enge, A.; Fukuda, K. (2000). «Exact Volume Computation for Polytopes: A Practical Study». Polytopes — Combinatorics and Computation. p. 131. ISBN 978-3-7643-6351-2. doi:10.1007/978-3-0348-8438-9_6.

[9] Yao, Andrew Chi Chih (1981), «A lower bound to finding convex hulls», Journal of the ACM 28 (4): 780-787, MR 677089, doi:10.1145/322276.322289 .; Ben-Or, Michael (1983), «Lower Bounds for Algebraic Computation Trees», Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (STOC '83), pp. 80-86, doi:10.1145/800061.808735 ..

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]