Polítopo convexo

Um politopo convexo é um caso especial de um politopo, tendo a propriedade adicional que é também um jogo convexo dos pontos no espaço n-dimensional Rⁿ.^[1] Alguns autores usam os termos "politopo convexo" e "poliedro convexo" de forma intercambiável, enquanto outros preferem fazer uma distinção entre as noções de um poliedro e um politopo.

Além disso, alguns textos exigem que um politopo seja um conjunto limitado, enquanto outros ^[2] (incluindo este artigo) permitem que os politopos sejam ilimitados. Os termos "politopo convexo delimitado / ilimitado" serão usados abaixo sempre que o limite seja crítico para a questão discutida. No entanto, outros textos tratam um n-politopo convexo como uma superfície.

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

Um livro abrangente e influente sobre o assunto, chamado Convex Polytopes, foi publicado em 1967 por Branko Grünbaum. Em 2003, a 2ª edição do livro foi publicado, com material adicional significativo, com contribuição de novos escritores. ^[1]

No livro de Grünbaum, e em alguns outros textos na geometria discreta, os politopos convexos são chamados simplesmente simplesmente "politopos". Grünbaum aponta que isso é apenas para evitar a repetição sem fim da palavra "convexo", e que a discussão deve ser entendida como se aplicando apenas à variedade convexa.

Um politopo é chamado em todas as dimensões, se esse é um objeto n-dimensional, em Rⁿ .

Exemplos[editar | editar código-fonte]

Muitos exemplos de politopos convexos delimitados podem ser encontrados no artigo "poliedro".
No caso bidimensional, os exemplos de dimensão total são um meio plano, uma faixa entre duas linhas paralelas, uma forma de ângulo (a interseção de dois semiplanos não paralelos), uma forma definida por uma cadeia poligonal convexa com dois Raios unidos às suas extremidades, e um polígono convexo.
Os casos especiais de um politopo convexo ilimitado são uma laje entre dois hiperplanos paralelos, uma cunha definida por dois semiespaços não paralelos, um cilindro poliédrico (prisma infinito) e um cone poliédrico (cone infinito) definido por três ou mais meio- espaços que passam por um ponto comum.

Definições[editar | editar código-fonte]

Um politopo convexo pode ser definido de várias maneiras, dependendo do que é 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 semiespaço (representação do semiespaço) e como o casco convexo de um conjunto de pontos (representação de vértices).

Representação de vértices (casco convexo)[editar | editar código-fonte]

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

Um conjunto K de Rⁿ é convexo se, para cada par de pontos distintos a, b em K, o segmento fechado com pontos extremos a e b estiver contido dentro de K.

Isso equivale a definir um politopo convexo acotado como o casco convexo 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értices (representação-V ou descrição-V). ^[1] Para um politopo convexo compacto, a descrição V mínima é única e é dada pelo conjunto dos vértices do politopo. ^[1]

Intersecção de semiespaço[editar | editar código-fonte]

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

Um semiespaço fechado pode ser escrito como uma desigualdade linear: ^[1]

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

Onde n é a dimensão do espaço que contém o politopo em consideração. Assim, um politopo convexo fechado pode ser considerado como o conjunto de soluções para o sistema de desigualdades lineares:

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

Onde m é o número de semiespaços que definem o politopo. Isso pode ser escrito concisamente como uma desigualdade matricial:

Ax\leq b

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 A e b correspondem aos coeficientes da desigualdade linear que define o respectivo semiespaço. Assim, cada linha na matriz corresponde a um hiperplano de suporte do politopo, um hiperplano que delimita um semiespaço que contém o politopo. Se um hiperplano de suporte também intercepta o politopo, ele é chamado de hiperplano delimitador (já que é um hiperplano de suporte, ele só pode cruzar o politopo no limite do politopo).

A definição anterior supõe que o politopo é n-dimensional. Se não for, então a solução de Ax ≤ b está em um subespaço afim apropriado de Rⁿ e a discussão do politopo pode ser restringida a este subespaço.

Em geral, a intersecção de semiespaços arbitrários não precisa ser limitada. No entanto, se se deseja ter uma definição equivalente àquela como um casco convexo, então bounding deve ser explicitamente exigido.

A definição acima pressupõe que o politopo está em todas dimensões. Se não for, então a solução de Ax ≤ b Encontra-se em um subespaço afim apropriado de Rⁿ e a discussão do politopo pode ser restringida a este subespaço.

Em geral, a intersecção de semiespaços arbitrários não precisa ser limitada. No entanto, se deseja ter uma definição equivalente àquela como um casco convexo, então o delimitador deve ser explicitamente exigido.

Teorema da base finita[editar | editar código-fonte]

O teorema de base finita ^[2] é uma extensão da noção de descrição V para incluir politopos infinitos. O teorema afirma que um poliedro convexo é a soma convexa de seus vértices mais a soma cônica dos vetores de direção de suas bordas infinitas.

Propriedades[editar | editar código-fonte]

Cada politopo convexo (limitado) é a imagem de um simplex, como cada ponto é uma combinação convexa dos (finitamente muitos) vértices. Entretanto, os politopos não são em geral isomórficos aos simples. Isto é em contraste com o caso de espaços vetoriais e combinações lineares, sendo cada espaço vetorial de dimensões finitas não apenas uma imagem de um espaço euclidiano de alguma dimensão (ou análogo sobre outros campos), mas de fato isomórfico.

O reticulado das faces[editar | editar código-fonte]

Uma face de um polítopo convexo é qualquer interseção do politopo com um semiespaço tal que nenhum dos pontos interiores do politopo encontra-se no limite do semiespaço. Se um politopo é d-dimensional, suas facetas são suas faces (d-1) -dimensionais, seus vértices são suas faces 0-dimensionais, suas bordas são suas faces unidimensionais, e seus cumes são seus (d - 2) faces dimensional.

Dado um politopo convexo P definido pela desigualdade matricial $Ax\leq b,$ se cada linha em A corresponde a um hiperplano delimitador e for 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 determinada faceta irá satisfazer a igualdade linear da linha correspondente na matriz. (Pode ou não também, satisfazer a igualdade em outras linhas). Da mesma forma, cada ponto em um cume vai satisfazer a igualdade em duas das linhas de A.

Em geral, uma face (n - j) -dimensional satisfaz a igualdade em j linhas específicas de A. Estas linhas formam uma base da face. Geometricamente falando, isso significa que a face é o conjunto de pontos no politopo que se encontram na interseção de j dos hiperplanos limitadores do politopo. A grade de face de uma pirâmide quadrada, desenhada como um diagrama de Hasse; Cada face na rede é rotulada pelo seu conjunto de vértices.

Em geral, uma face (n - j) -dimensional satisfaz a igualdade em j linhas específicas de A. Estas linhas formam uma base da face. Geometricamente falando, isto significa que a face é o conjunto de pontos no politopo que se encontram na intersecção de j dos hiperplanos limitadores do politopo.

As faces de um politopo convexo formam assim uma estrutura Euleriana chamada sua grade de face, onde a ordenação parcial é por conjunto a contenção de faces. A definição de uma face dada acima permite que tanto o próprio politopo como o conjunto vazio sejam considerados como faces, garantindo que cada par de faces tenha uma união e uma reunião na rede da face. O politopo inteiro é o único elemento máximo da rede, e o conjunto vazio, considerado uma face (-1) -dimensional (um politopo nulo) de cada politopo, é o único elemento mínimo da rede.^[3]

Dois polítopos são considerados combinatoriamente isomorfos se seus reticulados de faces forem isomorfos.

O gráfico politópico (gráfico politópico, gráfico do politopo, 1-esqueleto) é o conjunto de vértices e arestas do politopo apenas, ignorando as faces de dimensões superiores. Por exemplo, um gráfico poliédrico é o gráfico politópico de um politopo tridimensional. Por um resultado de Whitney [1] a estrutura de face de um polytope tridimensional é determinada por seu gráfico. O mesmo é verdadeiro para os polytopes simples da dimensão arbitrária (Blind & Mani-Levitska 1987, provando uma conjectura de Micha Perles).^[4] [2] Kalai (1988) ^[5] fornece uma prova simples baseada em orientações de sumidouros únicas. Como as telas de face dos politopos são determinadas por seus gráficos, o problema de decidir se dois politopos convexos tridimensionais ou simples são combinatoriamente isomórficos pode ser formulado equivalentemente como um caso especial do problema do isomorfismo do gráfico. No entanto, também é possível traduzir esses problemas na direção oposta, mostrando que o teste de isomorfismo de politopos é o grafo-isomorfismo completo.^[6]

Propriedades topologicas[editar | editar código-fonte]

Um politopo convexo, como qualquer subconjunto convexo fechado de Rⁿ, É homeomorfo a uma bola fechada. ^[7] Seja m a dimensão do politopo. Se o politopo for full-dimensional, então m = n. O politopo convexo é consequentemente um m-dimensional colector com limite, sua característica de Euler é 1, e seu grupo fundamental é trivial. O limite do politopo convexo é homeomorfo a uma esfera (m - 1). A característica de Euler do limite é 0 para m par e 2 para m ímpar. O limite também pode ser considerado como um tessellation do espaço esférico (m - 1)-dimensional - isto é, como um revestimento esférico.

Decomposição Simplicial[editar | editar código-fonte]

Um politopo convexo pode ser decomposto em um complexo simplicial, ou união de simplicial, satisfazendo certas propriedades.

Dado um politopo convexo r-dimensional P, um subconjunto de seus vértices contendo (r + 1) pontos afins independentes define um r-simplex. É possível formar uma coleção de subconjuntos de tal forma que a união dos correspondentes simplicial seja igual a P, e a interseção de quaisquer dois simplismos seja vazia ou um simplex de menor dimensão. 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.^[8]

Problemas algorítmicos para um politopo convexo[editar | editar código-fonte]

Construção de representações[editar | editar código-fonte]

As representações diferentes de um politopo convexo têm a utilidade diferente, consequentemente a construção de uma representação dada outra é um problema importante. O problema da construção de uma representação em V é conhecido como o problema de enumeração de vértices e o problema da construção de uma representação em H é conhecido como o problema de enumeração de faceta. Embora o conjunto de vértices de um politopo convexo limitado o defina unicamente, em várias aplicações é importante saber mais sobre a estrutura combinatória do politopo, isto é, sobre a sua estrutura de face. Vários algoritmos convexos do casco tratam ambos com a enumeração de faceta e a construção da estrutura da face.

No caso planar, i.e., para um polígono convexo, os problemas de enumeração de faceta e de vértice correspondem aos vértices de ordenação (respectivamente arestas) ao redor do casco convexo. É uma tarefa trivial quando o polígono convexo é especificado de uma maneira tradicional para polígonos, isto é, pela seqüência ordenada de seus vértices $v_{1},\dots ,v_{m}.$ Quando a lista de entrada de vértices (ou arestas) é desordenada, a complexidade temporal dos problemas torna-se O (m log m). ^[9]Um limite inferior correspondente é conhecido no modelo algébrico da árvore de decisão da computação.^[10]

Ver também[editar | editar código-fonte]

↑ ^a ^b ^c ^d ^e ^f ^g Branko Grünbaum, Convex Polytopes, 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. 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. Consultado em 11 de janeiro de 2017. Arquivado do original em 21 de julho 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. [S.l.: s.n.] 131 páginas. ISBN 978-3-7643-6351-2. doi:10.1007/978-3-0348-8438-9_6
↑ Predefinição:Introduction to Algorithms
↑ 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 .

[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 M. 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. Consultado em 11 de janeiro de 2017. Arquivado do original em 21 de julho 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. [S.l.: s.n.] 131 páginas. ISBN 978-3-7643-6351-2. doi:10.1007/978-3-0348-8438-9_6

[9] Predefinição:Introduction to Algorithms

[10] 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]

[10]