Politopo convexo

Envolvente convexa de un conjunto finito de puntos en un espacio euclidiano

Un politopo convexo tridimensional

Un politopo convexo es un caso especial de politopo , que tiene la propiedad adicional de que también es un conjunto convexo contenido en el espacio euclidiano de dimensión 1. La mayoría de los textos ^{[1] [2]} utilizan el término "politopo" para un politopo convexo acotado , y la palabra "poliedro" para el objeto más general, posiblemente ilimitado. Otros ^[3] (incluido este artículo) permiten que los politopos sean ilimitados. Los términos "politopo convexo acotado/ilimitado" se utilizarán a continuación siempre que la acotación sea crítica para el tema discutido. Sin embargo, otros textos identifican un politopo convexo con su límite. ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

Los politopos convexos juegan un papel importante tanto en diversas ramas de las matemáticas como en áreas aplicadas, más notablemente en la programación lineal .

En los influyentes libros de texto de Grünbaum ^[1] y Ziegler ^[2] sobre el tema, así como en muchos otros textos de geometría discreta , los politopos convexos a menudo se denominan simplemente "politopos". Grünbaum señala que esto se hace únicamente para evitar la repetición interminable de la palabra "convexo", y que la discusión a lo largo del texto debe entenderse como aplicable únicamente a la variedad convexa (p. 51).

Un politopo se denomina de dimensión completa si es un objeto de dimensión . ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$

Ejemplos

• Se pueden encontrar muchos ejemplos de politopos convexos acotados en el artículo " poliedro ".
• En el caso bidimensional, los ejemplos de dimensión completa son un semiplano , una franja entre dos líneas paralelas, una forma angular (la intersección de dos semiplanos no paralelos), una forma definida por una cadena poligonal convexa con dos rayos unidos a sus extremos y un polígono convexo .
• Casos especiales de un politopo convexo ilimitado son una losa entre dos hiperplanos paralelos, una cuña definida por dos semiespacios no paralelos , un cilindro poliédrico ( 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 puede definirse de varias maneras, dependiendo de lo que sea más adecuado para el problema en cuestión. La definición de Grünbaum se refiere a un conjunto convexo de puntos en el espacio. Otras definiciones importantes son: como la intersección de semiespacios (representación de semiespacio) y como la envoltura convexa de un conjunto de puntos (representación de vértice).

Representación de vértices (envolvente convexa)

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 de es convexo si, para cada par de puntos distintos , en , el segmento cerrado con extremos y está contenido dentro de . ${\displaystyle K}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle K}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle K}$

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

Intersección de semiespacios

Un politopo convexo puede definirse como una intersección de un número finito de semiespacios. Esta definición se denomina representación de semiespacio ( 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 de hecho única y está dada por el conjunto de semiespacios que definen facetas . ^[1]

Un semiespacio cerrado puede escribirse como una desigualdad lineal : ^[1]

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

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

${\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 es el número de semiespacios que definen el politopo. Esto se puede escribir de forma concisa como la desigualdad matricial : ${\displaystyle m}$

${\displaystyle Ax\leq b}$

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

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

Los coeficientes de cada fila de y corresponden a los coeficientes de la desigualdad lineal que define el semiespacio respectivo. Por lo tanto, cada fila de la matriz corresponde a un hiperplano de soporte del politopo, un hiperplano que delimita un semiespacio que contiene el politopo. Si un hiperplano de soporte también interseca al politopo, se denomina hiperplano delimitador (ya que es un hiperplano de soporte, solo puede intersecar al politopo en el límite del politopo). ${\displaystyle A}$ ${\displaystyle b}$

La definición anterior supone que el politopo es de dimensión completa. En este caso, existe un único conjunto mínimo de desigualdades definitorias (hasta la multiplicación por un número positivo). Las desigualdades que pertenecen a este único sistema mínimo se denominan desigualdades 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 se encuentran en un subespacio afín propio de y el politopo puede estudiarse como un objeto en este subespacio. En este caso, existen ecuaciones lineales que son satisfechas por todos los puntos del politopo. Agregar una de estas ecuaciones a cualquiera de las desigualdades definitorias no cambia el politopo. Por lo tanto, en general no hay un conjunto mínimo único de desigualdades que definan el politopo. ${\displaystyle Ax\leq b}$ ${\displaystyle \mathbb {R} ^{n}}$

En general, no es necesario acotar la intersección de semiespacios arbitrarios. Sin embargo, si se desea tener una definición equivalente a la de una envoltura convexa, entonces se debe exigir explícitamente la delimitación.

Equivalencia con la representación del vértice

Al exigir que la intersección de semiespacios dé como resultado un conjunto acotado, la definición se vuelve equivalente a la representación de vértices. ^[4] A continuación se presenta un esquema de la prueba de que la intersección acotada de semiespacios da como resultado un politopo en representación de vértices:

La intersección acotada de semiespacios cerrados de es claramente compacta y convexa. Un conjunto compacto y convexo con un número finito de puntos extremos debe ser un politopo, donde esos puntos extremos forman el conjunto de vértices. Queda por demostrar que el conjunto de puntos extremos (de la intersección acotada de un conjunto finito de semiespacios) también es finito: ${\displaystyle \mathbb {R} ^{n}}$

Sea un punto extremo de , la intersección acotada de semiespacios cerrados . Consideramos la intersección de todos los hiperplanos correspondientes (que dividen el espacio en los semiespacios) que contienen a . Esto produce un subespacio afín . Para cada semiespacio donde el hiperplano no contiene a , consideramos la intersección del interior de esos semiespacios. Esto produce un conjunto abierto . Claramente, . Como es un punto extremo de y es relativamente abierto , se deduce que debe ser 0-dimensional y . Si no fuera 0-dimensional, sería el punto interior de (al menos) una línea, lo que contradice ser un punto extremo. Como cada construcción de elige el interior o el límite de uno de los semiespacios cerrados, solo hay un número finito de conjuntos diferentes . Cada punto extremo se encuentra en uno de estos conjuntos, lo que significa que la cantidad de puntos extremos es finita. ${\displaystyle x\in {\textrm {ext}}(P)}$ ${\displaystyle P:=\bigcap _{i=1}^{k}H_{i}}$ ${\displaystyle H_{i}}$ ${\displaystyle x}$ ${\displaystyle U}$ ${\displaystyle x}$ ${\displaystyle O}$ ${\displaystyle x\in (U\cap O)\subseteq P}$ ${\displaystyle x}$ ${\displaystyle P}$ ${\displaystyle D:=U\cap O}$ ${\displaystyle D}$ ${\displaystyle D=\left\{x\right\}}$ ${\displaystyle D}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle D}$ ${\displaystyle k}$ ${\displaystyle D}$

Utilizando las diferentes representaciones

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

Un punto sutil en la representación por vectores es que el número de vectores puede ser exponencial en la dimensión, por lo que la prueba de que un vector está en el politopo puede ser exponencialmente larga. Afortunadamente, el teorema de Carathéodory garantiza que cada vector en el politopo puede ser representado por un máximo de d +1 vectores definitorios, donde d es la dimensión del espacio.

Representación de politopos no acotados

Para un politopo ilimitado (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 ilimitado puede representarse como una suma de un politopo limitado y un cono poliédrico convexo . ^[6] En otras palabras, cada vector en un politopo ilimitado 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 llama el teorema de la base finita . ^[3]

Propiedades

Todo politopo convexo (acotado) es la imagen de un símplex , ya que cada punto es una combinación convexa de los (finitos) 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 todo espacio vectorial de dimensión finita no solo es una imagen de, sino que, de hecho, es isomorfo a, un espacio euclidiano de alguna dimensión (o análogo sobre otros cuerpos).

La celosía de la cara

Una cara de un politopo convexo es cualquier intersección del politopo con un semiespacio tal que ninguno de los puntos interiores del politopo se encuentre en el límite del semiespacio. De manera 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 , si cada fila de A se corresponde con un hiperplano delimitador y es linealmente independiente de las otras filas, entonces cada faceta de P se corresponde exactamente con una fila de A , y viceversa. 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 . ${\displaystyle Ax\leq b}$

La red de caras de una pirámide cuadrada , dibujada como un diagrama de Hasse ; cada cara de la red está etiquetada por su conjunto de vértices.

En general, una cara de dimensión ( n  −  j ) satisface la igualdad en j filas específicas de A. Estas filas forman una 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 de los hiperplanos que delimitan el politopo.

Las caras de un politopo convexo forman así una red euleriana llamada red de caras , donde el ordenamiento parcial se realiza mediante la contención de caras en el conjunto. La definición de cara dada anteriormente permite que tanto el propio politopo como el conjunto vacío se consideren como caras, lo que garantiza que cada par de caras tenga una unión y un encuentro 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 redes de caras son isomorfas .

El grafo politópico ( grafo politópico , grafo del politopo , 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. Por 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 & Mani-Levitska 1987, probando una conjetura de Micha Perles ). ^[8] Kalai (1988) ^[9] da una prueba simple basada en orientaciones de sumidero ú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 se puede formular de manera equivalente como un caso especial del problema de isomorfismo de grafos . Sin embargo, también es posible traducir estos problemas en la dirección opuesta, mostrando que la prueba de isomorfismo de politopo es un isomorfismo de grafo completo. ^[10]

Propiedades topológicas

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 borde, su característica de Euler es 1 y su grupo fundamental es trivial. El borde del politopo convexo es homeomorfo a una ( m  − 1)-esfera . La característica de Euler del borde es 0 para m par y 2 para m impar . El borde también puede considerarse como una teselación de un espacio esférico de ( m  − 1)-dimensional —es decir, como un mosaico esférico .

Descomposición simple

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

Dado un politopo convexo de dimensión r P , un subconjunto de sus vértices que contiene ( r +1) puntos afínmente independientes define un r -símplice . Es posible formar una colección de subconjuntos de modo 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ímplice de dimensión inferior. 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ímplice se da fácilmente mediante una fórmula. ^[12]

Tijeras-congruencia

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

Problemas algorítmicos para un politopo convexo

Construcción de representaciones

Las diferentes representaciones de un politopo convexo tienen diferentes utilidades, por lo tanto, la construcción de una representación dada 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 manera única, en varias aplicaciones es importante saber más sobre la estructura combinatoria del politopo, es decir, sobre su red de caras. Varios algoritmos de envoltura convexa se ocupan tanto de la enumeración de facetas como de la construcción de la red de caras.

En el caso planar, es decir, para un polígono convexo , tanto los problemas de enumeración de facetas como de vértices equivalen 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 los polígonos , es decir, por la secuencia ordenada de sus vértices . 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 un límite inferior coincidente en el modelo de cálculo de árbol de decisión algebraico . ^[14] ${\displaystyle v_{1},\dots ,v_{m}}$

Cálculo de volumen

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 membresía . 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 bit que no es polinómica en esta representación. ^[15]

Véase también

• Matroide orientado
• Poliedro de Nef
• Teorema de Steinitz para poliedros convexos

Referencias

1. Branko Grünbaum , Politopos convexos , 2.ª edición, preparada por Volker Kaibel, Victor Klee y Günter M. Ziegler , 2003, ISBN  0-387-40409-0 , ISBN 978-0-387-40409-7 , 466pp. 
2. Ziegler, Günter M. (1995), Lecciones sobre politopos , Textos de posgrado en matemáticas, vol. 152, Berlín, Nueva York: Springer-Verlag.
3. Programación matemática , de Melvyn W. Jeter (1986) ISBN 0-8247-7478-7 , pág. 68 
4. Hug, Daniel; Weil, Wolfgang (2020). Lecciones sobre geometría convexa . Textos de posgrado en matemáticas. Cham, Suiza: Springer. pp. 30–35. ISBN 978-3-030-50180-8.
5. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549
6. Motzkin, Theodore (1936). Beitrage zur Theorie der linearen Ungleichungen (tesis doctoral) . Jerusalén.{{cite book}}: CS1 maint: location missing publisher (link)
7. Whitney, Hassler (1932). "Gráficos congruentes y la conectividad de grafos". Amer. J. Math . 54 (1): 150–168. doi :10.2307/2371086. hdl : 10338.dmlcz/101067 . JSTOR  2371086.
8. Ciego, Roswitha ; Mani-Levitska, Peter (1987), "Rompecabezas e isomorfismos de politopos", Aequationes Mathematicae , 34 (2–3): 287–297, doi :10.1007/BF01830678, MR  0921106, S2CID  120222616.
9. Kalai, Gil (1988), "Una forma sencilla de distinguir un politopo simple de su gráfico", Journal of Combinatorial Theory , Ser. A, 49 (2): 381–383, doi : 10.1016/0097-3165(88)90064-7 , MR  0964396.
10. Kaibel, Volker; Schwartz, Alexander (2003). "Sobre la complejidad de los problemas de isomorfismo de politopos". Graphs and Combinatorics . 19 (2): 215–230. arXiv : math/0106093 . doi :10.1007/s00373-002-0503-y. S2CID  179936. Archivado desde el original el 21 de julio de 2015.
11. Glen E. Bredon , Topología y geometría , 1993, ISBN 0-387-97926-3 , pág. 56. 
12. Büeler, B.; Enge, A.; Fukuda, K. (2000). "Cálculo exacto del volumen para politopos: un estudio práctico". Politopos: combinatoria y computación . págs. 131–154. doi :10.1007/978-3-0348-8438-9_6. ISBN 978-3-7643-6351-2.
13. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001) [1990]. "33.3 Hallazgo de la envoltura convexa". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. págs. 947–957. ISBN 0-262-03293-7.
14. Yao, Andrew Chi Chih (1981), "Un límite inferior para encontrar envolturas convexas", Journal of the ACM , 28 (4): 780–787, doi : 10.1145/322276.322289 , MR  0677089, S2CID  13846330; Ben-Or, Michael (1983), "Límites inferiores para árboles de computación algebraica", Actas del decimoquinto simposio anual de la ACM sobre teoría de la computación (STOC '83) , págs. 80-86, doi : 10.1145/800061.808735.
15. Lawrence, Jim (1991). "Cálculo del volumen de un politopo". Matemáticas de la computación . 57 (195): 259–271. Bibcode :1991MaCom..57..259L. doi : 10.1090/S0025-5718-1991-1079024-2 . ISSN  0025-5718.

Enlaces externos

• Weisstein, Eric W. "Polígono convexo". MathWorld .
• Weisstein, Eric W. "Poliedro convexo". MathWorld .
• Komei Fukuda , Preguntas frecuentes sobre cálculo poliédrico.