O envelope convexo de um objeto ou de um agrupamento de objetos geométricos é o menor conjunto convexo entre aqueles que o contêm.
Em um plano, o envelope convexo pode ser comparado à região delimitada por um elástico que abrange todos os pontos que se soltam até que se contraia ao máximo. A ideia seria a mesma no espaço com um balão que esvaziaria até entrar em contato com todos os pontos que estão na superfície do envelope convexo.
Suporemos estar em um contexto onde a noção de subconjunto convexo tem um significado (por exemplo, em geometria afim em números reais), e denotaremos por E a moldura geométrica em que nos colocamos.
Definição - De qualquer A parte E . O convexo envelope de A é a intersecção de todas as partes convexas para E , que contêm A .
Essa definição faz sentido, uma vez que há pelo menos uma parte convexa de E que contém A , a saber, o próprio E.
A partir dessa definição e do fato de que qualquer interseção de conjuntos convexos é um conjunto convexo, deduzimos a seguinte caracterização do casco convexo.
Movimento - O convexo envelope A é a menor parte convexa de E , que contém A .
Desenvolvido em mais detalhes, este resultado caracteriza o envelope convexo Conv ( A ) como o subconjunto exclusivo de E que satisfaz as três condições a seguir:
Por exemplo, Conv ( ∅ ) = ∅.
No restante desta seção, assumiremos que E é um espaço real afim . Podemos então afirmar:
Proposta - O envelope convexo de A é o conjunto de combinações convexas (ou seja, os centros de gravidade para coeficientes não negativos) das famílias de pontos de Uma .
Em outras palavras: os elementos do envelope convexo de A são exatamente os pontos x de E que podemos escrever na forma:
, Expressão em que p é um número inteiro, a um i são em Um , os coeficientes X i são reais positivos e de somaA afirmação acima pode ser aprimorada em dimensão finita, como notado por Constantine Carathéodory em 1907 . Se denotarmos por n a dimensão de E , o teorema afirma que podemos usar baricentros de p pontos limitando-nos ao caso p = n + 1 para reconstituir todo o envelope convexo. Assim, em um plano, dado A , construímos mentalmente seu envelope convexo escurecendo pelo pensamento todos os triângulos com vértices em A ; na dimensão 3 usaríamos tetraedros, e assim por diante.
O teorema é afirmado precisamente da seguinte forma:
Teorema - Em um espaço afim de dimensão N , do envelope convexo um subconjunto Um é um conjunto de combinações convexas de famílias de n + 1 pontos de Uma .
Uma vez que esta afirmação é conhecida, é fácil deduzir um corolário importante:
Corolário - Em um espaço afim de dimensão finita, o envelope convexo de um compacto é compacto.
(Considerando que por exemplo no espaço de Hilbert ℓ 2 , de base Hilbertiana ( δ n ) n ∈ℕ , a seqüência (δ n / n ) n ∈ℕ e seu limite 0 formam um compacto , cujo envelope convexo n nem sequer é fechado . )
O cálculo do envelope convexo de um conjunto de pontos é um problema clássico em geometria computacional. Vários algoritmos foram inventados para resolver este problema, sua complexidade varia:
Para um conjunto finito de pontos, o casco convexo é um poliedro convexo. Porém, sua representação não é tão fácil como no caso do plano. Para dimensões estritamente maiores que 2, mesmo que as arestas do poliedro sejam conhecidas, a construção das facetas não é uma tarefa trivial. Um certo número de algoritmos ainda são conhecidos para a dimensão 3, mas também no caso geral.
(pt) Convex Hull Algorithms , miniaplicativo Java 3D
<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">