Yhyjyk

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 |

• 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 |

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) |

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 |

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]

a1x1+a2x2+⋯+anxn≤bdisplaystyle a_1x_1+a_2x_2+cdots +a_nx_nleq b

a11x1+a12x2+⋯+a1nxn≤b1a21x1+a22x2+⋯+a2nxn≤b2⋮⋮⋮⋮am1x1+am2x2+⋯+amnxn≤bmdisplaystyle beginalignedat7a_11x_1&&;+;&&a_12x_2&&;+cdots +;&&a_1nx_n&&;leq ;&&&b_1\a_21x_1&&;+;&&a_22x_2&&;+cdots +;&&a_2nx_n&&;leq ;&&&b_2\vdots ;;;&&&&vdots ;;;&&&&vdots ;;;&&&&&;vdots \a_m1x_1&&;+;&&a_m2x_2&&;+cdots +;&&a_mnx_n&&;leq ;&&&b_m\endalignedat

Ax≤bdisplaystyle Axleq b

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 |

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 |

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 |

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 Ax≤b,displaystyle Axleq 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 |

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 |

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 |

Construção de representações |

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 v1,…,vm.displaystyle 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 |

• Poliedro


• Característica de Euler


• 
  Branko Grünbaum
  
  

↑ 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