Politopo convexo - Convex polytope

Um politopo convexo tridimensional

Um politopo convexo é um caso especial de politopo , tendo a propriedade adicional de ser também um conjunto convexo contido no espaço euclidiano dimensional . A maioria dos textos usa o termo "politopo" para um politopo convexo limitado e a palavra "poliedro" para o objeto mais geral, possivelmente ilimitado. Outros (incluindo este artigo) permitem que os politopos sejam ilimitados. Os termos "politopo convexo limitado / ilimitado" serão usados a seguir sempre que a limitação for crítica para o assunto discutido. Ainda outros textos identificam um politopo convexo com sua fronteira. ${\ displaystyle n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$

Os politopos convexos desempenham um papel importante em vários ramos da matemática e em áreas aplicadas, mais notavelmente na programação linear .

Nos influentes livros didáticos de Grünbaum e Ziegler sobre o assunto, bem como em muitos outros textos de geometria discreta , os politopos convexos são frequentemente chamados de "politopos". Grünbaum aponta que isso é apenas para evitar a repetição infinita da palavra "convexo", e que a discussão deve ser entendida como se aplicando apenas à variedade convexa (p. 51).

Um politopo é chamado de dimensional total se for um objeto dimensional em . ${\ displaystyle n}$ ${\ displaystyle \ mathbb {R} ^ {n}}$

Exemplos

Muitos exemplos de politopos convexos limitados podem ser encontrados no artigo " poliedro ".
No caso bidimensional, os exemplos dimensionais completos são um meio plano , uma faixa entre duas linhas paralelas, uma forma angular (a interseção de dois semiplanos não paralelos), uma forma definida por uma cadeia poligonal convexa com dois raios presos às suas extremidades e um polígono convexo .
Casos particulares de um poliepítopo convexa ilimitada são uma laje entre duas hiperplanos paralelas, uma cunha definida por dois não-paralelas meios espaços , um cilindro poliédrico (infinito prisma ), e um cone de poliédrico (infinito cone ) definido por três ou mais meia espaços que passam por um ponto comum.

Definições

Um politopo convexo pode ser definido de várias maneiras, dependendo do que for mais adequado para o problema em questão. A definição de Grünbaum é em termos de um conjunto convexo de pontos no espaço. Outras definições importantes são: como a interseção de meios-espaços (representação de meio-espaços ) e como o casco convexo de um conjunto de pontos (representação de vértices).

Representação de vértice (casco convexo)

Em seu livro Convex Polytopes , Grünbaum define um politopo convexo como um conjunto convexo compacto com um número finito de pontos extremos :

Um conjunto de é convexo se, para cada par de pontos distintos , em , o segmento fechado com pontos finais e estiver contido em .

{\ displaystyle K}

{\ displaystyle \ mathbb {R} ^ {n}}

{\ displaystyle a}

{\ displaystyle b}

{\ displaystyle K}

{\ displaystyle a}

{\ displaystyle b}

{\ displaystyle K}

Isso é equivalente a definir um politopo convexo limitado como a casca convexa de um conjunto finito de pontos, onde o conjunto finito deve conter o conjunto de pontos extremos do politopo. Tal definição é chamada de representação de vértice ( representação V ou descrição V ). Para um politopo convexo compacto, a descrição V mínima é única e é dada pelo conjunto dos vértices do politopo. Um politopo convexo é chamado de politopo integral se todos os seus vértices tiverem coordenadas inteiras.

Intersecção de meios-espaços

Um politopo convexo pode ser definido como uma interseção de um número finito de meios-espaços. Tal definição é chamada de representação de meio-espaço ( representação H ou descrição H ). Existem infinitas descrições H de um politopo convexo. No entanto, para um politopo convexo de dimensão total, a descrição H mínima é de fato única e é dada pelo conjunto de meios-espaços que definem as facetas .

Um meio-espaço fechado pode ser escrito como uma desigualdade linear :

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

onde é a dimensão do espaço que contém o politopo em consideração. Portanto, um politopo convexo fechado pode ser considerado como o conjunto de soluções para o sistema de desigualdades lineares : ${\ displaystyle n}$

{\ displaystyle {\ begin {alignat} {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 {alignat}}}

onde é o número de meios-espaços que definem o politopo. Isso pode ser escrito de forma concisa como a desigualdade da matriz : ${\ displaystyle m}$

{\ displaystyle Ax \ leq b}

onde é uma matriz, é um vector de coluna cujas coordenadas são as variáveis a , e é um vector de coluna cujas coordenadas são os lados da mão direita para as 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}}$

Um politopo convexo aberto é definido da mesma maneira, com desigualdades estritas usadas nas fórmulas em vez das não estritas.

Os coeficientes de cada linha de e correspondem aos coeficientes da desigualdade linear definindo o respectivo meio-espaço. Portanto, cada linha na matriz corresponde a um hiperplano de suporte do politopo, um hiperplano que delimita um meio-espaço que contém o politopo. Se um hiperplano de suporte também interceptar o politopo, ele é chamado de hiperplano delimitador (uma vez que é um hiperplano de suporte, ele só pode interceptar o politopo no limite do politopo). ${\ displaystyle A}$ ${\ displaystyle b}$

A definição anterior assume que o politopo é totalmente dimensional. Nesse caso, há um conjunto mínimo único de desigualdades definidoras (até a multiplicação por um número positivo). As desigualdades pertencentes a este sistema mínimo único são chamadas de essenciais . O conjunto de pontos de um politopo que satisfaz uma desigualdade essencial com igualdade é chamado de faceta .

Se o politopo não for totalmente dimensional, as soluções de encontram-se em um subespaço afim apropriado de e o politopo pode ser estudado como um objeto neste subespaço. Neste caso, existem equações lineares que são satisfeitas por todos os pontos do politopo. Adicionar uma dessas equações a qualquer uma das desigualdades de definição não altera o politopo. Portanto, em geral, não existe um conjunto mínimo único de desigualdades definindo o politopo. ${\ displaystyle Ax \ leq b}$ ${\ displaystyle \ mathbb {R} ^ {n}}$

Em geral, a interseção de meios-espaços arbitrários não precisa ser limitada. No entanto, se alguém deseja ter uma definição equivalente à de um casco convexo, então a delimitação deve ser explicitamente exigida.

Usando as diferentes representações

As duas representações juntas fornecem uma maneira eficiente de decidir se um determinado vetor está incluído em um determinado politopo convexo: para mostrar que ele está no politopo, é suficiente apresentá-lo como uma combinação convexa dos vértices do politopo (a descrição em V é usado); para mostrar que não está no politopo, é suficiente apresentar uma única desigualdade definidora que ele viola.

Um ponto sutil na representação por vetores é que o número de vetores pode ser exponencial na dimensão, de modo que a prova de que um vetor está no politopo pode ser exponencialmente longa. Felizmente, o teorema de Carathéodory garante que cada vetor no politopo pode ser representado por no máximo d +1 vetores definidores, onde d é a dimensão do espaço.

Representação de politopos ilimitados

Para um politopo ilimitado (às vezes chamado de poliedro), a descrição H ainda é válida, mas a descrição V deve ser estendida. Theodore Motzkin (1936) provou que qualquer politopo ilimitado pode ser representado como a soma de um politopo limitado e um cone poliédrico convexo . Em outras palavras, cada vetor em um politopo ilimitado é uma soma convexa de seus vértices (seus "pontos definidores"), mais uma soma cônica dos vetores euclidianos de suas bordas infinitas (seus "raios definidores"). Isso é chamado de teorema de base finita .

Propriedades

Cada politopo convexo (limitado) é a imagem de um simplex , pois cada ponto é uma combinação convexa dos vértices (finitos). No entanto, os politopos não são em geral isomórficos aos simplicos. Isso está em contraste com o caso de espaços vetoriais e combinações lineares , cada espaço vetorial de dimensão finita não sendo apenas uma imagem, mas de fato isomórfico, o espaço euclidiano de alguma dimensão (ou análogo a outros campos).

A estrutura do rosto

Uma face de um politopo convexo é qualquer intersecção do politopo com um meio- espaço, de modo que nenhum dos pontos internos do politopo se encontre no limite do meio-espaço. De forma equivalente, uma face é o conjunto de pontos que dão igualdade em alguma desigualdade válida do politopo.

Se um politopo é d- dimensional, suas facetas são suas faces ( d - 1) -dimensional, seus vértices são suas faces 0-dimensionais, suas arestas são suas faces unidimensionais e suas cristas são suas faces ( d - 2) - faces dimensionais.

Dado um politopo convexo P definido pela desigualdade de matriz , se cada linha em A corresponde a um hiperplano delimitador e é linearmente independente das outras linhas, então cada faceta de P corresponde exatamente a uma linha de A e vice-versa. Cada ponto em uma dada faceta irá satisfazer a igualdade linear da linha correspondente na matriz. (Pode ou não satisfazer a igualdade em outras linhas). Da mesma forma, cada ponto em um cume irá satisfazer a igualdade em duas das linhas de A . ${\ displaystyle Ax \ leq b}$

A estrutura da face de uma pirâmide quadrada , desenhada como um diagrama de Hasse ; cada face na rede é rotulada por seu conjunto de vértices.

Em geral, um ( n - j ) -dimensional satisfaz cara igualdade em j linhas específicas de Uma . Essas linhas formam a base do rosto. Falando geometricamente, isso significa que a face é o conjunto de pontos no politopo que se encontram na interseção de j dos hiperplanos delimitadores do politopo.

As faces de um politopo convexo, portanto, formam uma rede Euleriana chamada rede de faces , onde a ordenação parcial é feita por contenção de faces. A definição de uma face dada acima permite que o próprio politopo e o conjunto vazio sejam considerados como faces, garantindo que cada par de faces tenha uma junção e um encontro na estrutura da face. Todo o politopo é o elemento máximo único da rede, e o conjunto vazio, considerado uma face (-1) -dimensional (um politopo nulo ) de cada politopo, é o elemento mínimo único da rede.

Dois politopos são chamados combinatorialmente isomórficos se suas redes de faces forem isomórficas .

O gráfico poliepítopo ( gráfico polytopal , gráfico do poliepítopo , 1-esqueleto ) é o conjunto de vértices e arestas de apenas o poliepítopo, ignorando as faces de dimensão superior. Por exemplo, um gráfico poliédrico é o gráfico de politopo de um politopo tridimensional. Por um resultado de Whitney, a estrutura da face de um politopo tridimensional é determinada por seu gráfico. O mesmo é verdade para politopos simples de dimensão arbitrária (Blind & Mani-Levitska 1987, provando uma conjectura de Micha Perles ). Kalai (1988) fornece uma prova simples baseada em orientações únicas de pia . Como as redes de face desses politopos são determinadas por seus gráficos, o problema de decidir se dois politopos tridimensionais ou convexos simples são combinatorialmente isomórficos pode ser formulado de forma equivalente como um caso especial do problema de isomorfismo de grafos . No entanto, também é possível traduzir esses problemas na direção oposta, mostrando que o teste de isomorfismo de politopo é isomorfismo de gráfico completo.

Propriedades topológicas

Um politopo convexo, como qualquer subconjunto convexo compacto de R ⁿ , é homeomórfico a uma bola fechada . Seja m a dimensão do politopo. Se o politopo for totalmente dimensional, então m = n . O politopo convexo, portanto, é uma variedade m- dimensional com limite, sua característica de Euler é 1 e seu grupo fundamental é trivial. O limite do politopo convexo é homeomórfico a uma ( m - 1) -sfera . Euler característica do limite é 0 para até m e 2 para ímpar m . A fronteira também pode ser considerada como um mosaico de espaço esférico ( m - 1) -dimensional - isto é, como um mosaico esférico .

Decomposição Simplicial

Um poliepítopo convexa pode ser decomposta em uma simplicial complexo , ou união de simplices , satisfazer determinadas propriedades.

Dado um politopo P convexo r- dimensional , um subconjunto de seus vértices contendo ( r +1) pontos afinamente independentes define um r -simplex . É possível formar uma coleção de subconjuntos de modo que a união dos simplicos correspondentes seja igual a P , e a interseção de quaisquer dois simplicos seja vazia ou um simplex de dimensão inferior. Esta decomposição simplicial é a base de muitos métodos para calcular o volume de um politopo convexo, uma vez que o volume de um simplex é facilmente dado por uma fórmula.

Problemas de algoritmo para um politopo convexo

Construção de representações

Diferentes representações de um politopo convexo têm diferentes utilidades, portanto, a construção de uma representação a partir de outra é um problema importante. O problema da construção de uma representação V é conhecido como problema de enumeração de vértices e o problema da construção de uma representação H é conhecido como problema de enumeração de facetas . Embora o conjunto de vértices de um politopo convexo limitado o defina de maneira única, em várias aplicações é importante saber mais sobre a estrutura combinatória do politopo, ou seja, sobre sua estrutura de face. Vários algoritmos de casco convexo lidam tanto com a enumeração de facetas quanto com a construção da estrutura de faces.

No caso plano, isto é, para um polígono convexo , os problemas de enumeração de facetas e vértices correspondem aos vértices de ordenação (arestas respectivamente) ao redor do casco convexo. É uma tarefa trivial quando o polígono convexo é especificado de forma tradicional para polígonos , ou seja, pela seqüência ordenada de seus vértices . Quando a lista de entrada de vértices (ou arestas) é desordenada, a complexidade de tempo dos problemas torna-se O ( m log m ). Um limite inferior correspondente é conhecido no modelo de cálculo de árvore de decisão algébrica . ${\ displaystyle v_ {1}, \ dots, v_ {m}}$

Computação de volume

A tarefa de calcular o volume de um politopo convexo foi estudada no campo da geometria computacional . O volume pode ser calculado aproximadamente , por exemplo, usando a técnica de aproximação de volume convexo , ao ter acesso a um oráculo de associação . Quanto ao cálculo exato , um obstáculo é que, quando dada uma representação do politopo convexo como um sistema de equações de desigualdades lineares , o volume do politopo pode ter um comprimento de bit que não é polinomial nesta representação.

Languages

In other projects