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 dimensional . 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.
Los politopos convexos desempeñan un papel importante tanto en diversas ramas de las matemáticas como en áreas aplicadas, sobre todo 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 sobre geometría discreta , los politopos convexos a menudo se denominan simplemente "politopos". Grünbaum señala que esto es únicamente para evitar la repetición interminable de la palabra "convexo", y que la discusión debe entenderse en todo momento como aplicable sólo a la variedad convexa (p. 51).
Un politopo se llama de dimensión completa si es un objeto de dimensión completa .
Un politopo convexo se puede definir de varias maneras, dependiendo de cuál 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 intersección de semiespacios (representación de semiespacio) y como casco convexo de un conjunto de puntos (representación de vértice).
En su libro Convex Polytopes , Grünbaum define un politopo convexo como un conjunto convexo compacto con un número finito de puntos extremos :
Esto equivale a definir un politopo convexo acotado como la cáscara convexa de un conjunto finito de puntos, donde el conjunto finito debe contener el conjunto de puntos extremos del politopo. Esta definición se denomina representación de vértice ( representación V o descripción V ). [1] Para un politopo convexo compacto, la descripción V mínima es única y viene dada por el conjunto de los vértices del politopo. [1] Un politopo convexo se llama politopo integral si todos sus vértices tienen coordenadas enteras.
Un politopo convexo puede definirse como una intersección de un número finito de semiespacios. Esta definición se denomina representación de medio espacio ( 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 las facetas . [1]
Un semiespacio cerrado se puede escribir como una desigualdad lineal : [1]
donde es la dimensión del espacio que contiene el politopo considerado. Por tanto, un politopo convexo cerrado puede considerarse como el conjunto de soluciones del sistema de desigualdades lineales :
donde es el número de semiespacios que definen el politopo. Esto se puede escribir de manera concisa como la desigualdad matricial :
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.
Un politopo convexo abierto se define de la misma manera, utilizándose desigualdades estrictas en las fórmulas en lugar de desigualdades no estrictas.
Los coeficientes de cada fila de y se corresponden con los coeficientes de la desigualdad lineal que define el medio espacio respectivo. Por lo tanto, cada fila de la matriz se corresponde con un hiperplano de soporte del politopo, un hiperplano que limita un semiespacio que contiene el politopo. Si un hiperplano de soporte también intersecta el politopo, se llama hiperplano delimitador (dado que es un hiperplano de soporte, solo puede intersectar el politopo en el límite del politopo).
La definición anterior supone que el politopo es de dimensiones completas. En este caso, existe un conjunto mínimo único de desigualdades definitorias (hasta la 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 con igualdad una desigualdad esencial se llama 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 se puede estudiar como un objeto en este subespacio. En este caso, existen ecuaciones lineales que se satisfacen en 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 existe un conjunto mínimo único de desigualdades que definan el politopo.
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 casco convexo, entonces se debe exigir explícitamente la delimitación.
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értice. [4] A continuación se muestra un resumen de la prueba de que la intersección acotada de semiespacios da como resultado un politopo en representación de vértice:
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:
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 . Esto produce un subespacio afín . Para cada semiespacio donde el hiperplano no contiene , consideramos la intersección del interior de esos semiespacios. Esto produce un conjunto abierto . Claramente, . Dado que es un punto extremo de y es relativamente abierto , se deduce que debe ser de dimensión 0 y . Si no fuera de dimensión 0, sería el punto interior de (al menos) una línea, lo que contradice ser un punto extremo. Dado que cada construcción de elige el interior o el límite de uno de los semiespacios cerrados, sólo 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.
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 (la descripción V se utiliza); para demostrar que no está en el politopo, basta con presentar una única desigualdad definitoria que viole. [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 podría ser exponencialmente larga. Afortunadamente, el teorema de Carathéodory garantiza que cada vector en el politopo puede representarse como máximo por d +1 vectores que definen, donde d es la dimensión del espacio.
Para un politopo ilimitado (a veces llamado poliedro), la descripción H sigue siendo válida, pero la descripción V debe ampliarse. Theodore Motzkin (1936) demostró que cualquier politopo ilimitado puede representarse como la suma de un politopo acotado 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 teorema de la base finita . [3]
Cada politopo convexo (limitado) es la imagen de un simplex , ya que cada punto es una combinación convexa de (un finito) vértices. Sin embargo, los politopos no son en general isomorfos a los simples. Esto contrasta con el caso de los espacios vectoriales y las combinaciones lineales , en los que cada espacio vectorial de dimensión finita no es sólo una imagen, sino que de hecho es isomorfo al espacio euclidiano de alguna dimensión (o análogo a otros campos).
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 unidimensionales y sus crestas son sus ( d - 2)-. caras dimensionales.
Dado un politopo convexo P definido por la desigualdad matricial , si cada fila en A corresponde con un hiperplano delimitador y es linealmente independiente de las otras filas, entonces cada faceta de P corresponde exactamente con una fila de A , y viceversa. Cada punto de una faceta determinada 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 dimensional ( n − j ) satisface la igualdad en j filas específicas de A. Estas filas forman la base del rostro. 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 delimitadores del politopo.
Las caras de un politopo convexo forman así una red euleriana llamada red de caras , donde el ordenamiento parcial se realiza mediante contención de caras. La definición de cara dada anteriormente permite que tanto el politopo en sí como el conjunto vacío se consideren caras, asegurando que cada par de caras tenga una unión y un encuentro en la red de caras. El politopo completo es el elemento máximo único de la red, y el conjunto vacío, considerado una cara (−1) dimensional (un politopo nulo ) de cada politopo, es el elemento mínimo único de la red.
Dos politopos se llaman combinatoriamente isomorfos si sus redes de caras son isomorfas .
El gráfico de politopo ( gráfico politopal , gráfico del politopo , 1-esqueleto ) es el conjunto de vértices y aristas del politopo únicamente, ignorando las caras de dimensiones superiores. Por ejemplo, un gráfico poliédrico es el gráfico politopo de un politopo tridimensional. Según Whitney [7], la red de caras de un politopo tridimensional está determinada por su gráfico. Lo mismo ocurre con los politopos simples de dimensión arbitraria (Blind y Mani-Levitska 1987, demostrando una conjetura de Micha Perles ). [8] Kalai (1988) [9] ofrece una prueba sencilla basada en orientaciones únicas del fregadero . Debido a que las redes de caras de estos politopos están determinadas por sus gráficos, el problema de decidir si dos politopos tridimensionales o convexos simples son combinatoriamente isomórficos se puede formular de manera equivalente como un caso especial del problema de isomorfismo de gráficos . Sin embargo, también es posible traducir estos problemas en la dirección opuesta, mostrando que la prueba de isomorfismo de politopos es un isomorfismo de grafos completo. [10]
Un politopo convexo, como cualquier subconjunto convexo compacto de R n , es homeomorfo a una bola cerrada . [11] Sea m la dimensión del politopo. Si el politopo es de dimensiones completas, entonces m = n . Por lo tanto, el politopo convexo 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 pares y 2 para m impares . El límite también puede considerarse como un mosaico de espacio esférico de dimensiones ( m − 1) , es decir, como un mosaico esférico .
Un politopo convexo se puede descomponer en un complejo simplicial , o unión de simples , satisfaciendo ciertas propiedades.
Dado un politopo P convexo de r dimensiones , un subconjunto de sus vértices que contienen ( r +1) puntos afines independientes define un r -simplex . 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 simplex de dimensiones inferiores. 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 obtiene fácilmente mediante una fórmula. [12]
Diferentes representaciones de un politopo convexo tienen diferente utilidad, 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 problema de enumeración de vértices y el problema de la construcción de una representación H se conoce como problema de enumeración de facetas . Si bien el conjunto de vértices de un politopo convexo acotado lo define de manera única, en diversas aplicaciones es importante saber más sobre la estructura combinatoria del politopo, es decir, sobre su red de caras. Varios algoritmos de casco convexo se ocupan tanto de la enumeración de facetas como de la construcción de la red de caras.
En el caso plano, 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 (respectivamente, aristas) alrededor del casco convexo. Es una tarea trivial cuando el polígono convexo se especifica de la manera tradicional para los polígonos , es decir, mediante la secuencia ordenada de sus vértices . Cuando la lista de entrada de vértices (o aristas) está desordenada, la complejidad temporal de los problemas se vuelve O ( m log m ). [13] En el modelo de cálculo del árbol de decisión algebraico se conoce un límite inferior coincidente . [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 aproximadamente , 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 bits que no es polinómica en esta representación. [15]
{{cite book}}: CS1 maint: location missing publisher (link)