Polítopo convexo

Origem: Wikipédia, a enciclopédia livre.

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 Rn.[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 Rn .

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 semi-planos 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 Rn é 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]

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:
Onde m é o número de semiespaços que definem o politopo. Isso pode ser escrito concisamente como uma desigualdade matricial:
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 Rn 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 Axb Encontra-se em um subespaço afim apropriado de Rn 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.

O reticulado da face de uma pirâmide quadrada, representado como um diagrama de Hasse; cada face do reticulado é rotulada por seu conjunto de vértices.

Dado um politopo convexo P definido pela desigualdade matricial 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 Rn, É 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 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]

  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.
  2. a b 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/0106093Acessível livremente. doi:10.1007/s00373-002-0503-y. Consultado em 11 de janeiro de 2017. Arquivado do original em 21 de julho de 2015 
  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 .