Sobre convexo

La envolvente convexa de un objeto o de una agrupación de objetos geométricos es el conjunto convexo más pequeño entre los que lo contienen.

En un plano, la envolvente convexa se puede comparar con la región delimitada por una goma elástica que engloba todos los puntos que se liberan hasta que se contrae al máximo. La idea sería la misma en el espacio con un globo que se desinflaría hasta entrar en contacto con todos los puntos que están en la superficie de la envoltura convexa.

Definición y propiedades básicas

Supondremos estar en un contexto donde la noción de subconjunto convexo tiene un significado (por ejemplo en geometría afín sobre números reales), y denotaremos por E el marco geométrico en el que nos ubicamos.

Definición - Cualquiera de una parte de E . El convexa envolvente de A es la intersección de todas las partes convexas a E , que contienen A .

Esta definición tiene sentido, ya que hay al menos una parte convexa de E que contiene A , a saber, la propia E.

De esta definición y del hecho de que cualquier intersección de conjuntos convexos es un conjunto convexo, deducimos la siguiente caracterización del casco convexo.

Movimiento - El convexa envolvente Una es la más pequeña parte convexa de E que contiene una .

Desarrollado con más detalle, este resultado caracteriza la envolvente convexa $Conv$ ( A ) como el subconjunto único de E que satisface las siguientes tres condiciones:

$Conv$ ( A ) es convexo;
A está incluido en $Conv$ ( A );
Si C es un convexa subconjunto de E que contiene A , a continuación, $Conv$ ( A ) se incluye en C .

Por ejemplo, $Conv$ ( ∅ ) = ∅.

Descripción en términos de baricentros

En el resto de esta sección, asumiremos que E es un espacio afín real. Entonces podemos afirmar:

Propuesta - La envolvente convexa de A es el conjunto de combinaciones convexas (es decir, los centros de gravedad a coeficientes no negativos) de las familias de puntos de A .

En otras palabras: los elementos de la envolvente convexa de A son exactamente los puntos $x$ de E que se pueden escribir en la forma:

x = \ sum _ {{i = 1}} ^ {p} \ lambda _ {i} a_ {i}

, expresión en la que

p

es un número entero, los

a i

están en A , los coeficientes

λ i

son reales positivos y de suma

\ sum _ {{i = 1}} ^ {p} \ lambda _ {i} = 1.

El caso de la dimensión finita: un teorema de Carathéodory

La afirmación anterior puede mejorarse en una dimensión finita, como señaló Constantine Carathéodory en 1907 . Si denotamos por n la dimensión de E , el teorema establece que podemos usar baricentros de p puntos limitándonos al caso p = n + 1 para reconstituir toda la envolvente convexa. Así, en un plano, dado A , construimos mentalmente su envolvente convexa oscureciendo con el pensamiento todos los triángulos con vértices en A ; en la dimensión 3 usaríamos tetraedros, y así sucesivamente.

El teorema se establece precisamente como sigue:

Teorema - En un espacio afín de dimensión n , la convexa sobre un subconjunto A es un conjunto de combinaciones convexas de las familias de n + 1 puntos de A .

Una vez que se conoce esta afirmación, es fácil deducir un corolario importante:

Corolario : en un espacio afín de dimensión finita, la envoltura convexa de un compacto es compacta.

(Mientras que, por ejemplo, en el espacio de Hilbert ℓ 2 , de base Hilbertiana ( δ n ) n ∈ℕ , la secuencia (δ n / n ) n ∈ℕ y su límite 0 forman un compacto , cuya envolvente convexa n ni siquiera es cerrada . )

Aspectos algorítmicos

En 2D

El cálculo de la envolvente convexa de un conjunto de puntos es un problema clásico en geometría computacional. Se han inventado varios algoritmos para resolver este problema, su complejidad varía:

Jarvis caminar en , siendo el número de puntos de la envolvente convexa; ${\ Displaystyle O (nh)}$ $h$
Algoritmo de Chan , en  ; ${\ Displaystyle O (n \ log (h))}$
Curso de Graham , en ; $O (n \ log (n))$
heurística de Akl-Toussaint ;
usando el diagrama de Voronoi , en : los puntos de la envoltura convexa definen células de Voronoi abiertas, es suficiente detectar estas células y conectar los gérmenes de las células adyacentes. $O (n \ log (n))$

Dimensiones de orden superior

Para un conjunto finito de puntos, el casco convexo es un poliedro convexo. Sin embargo, su representación no es tan fácil como en el caso del plan. Para dimensiones estrictamente superiores a 2, incluso si se conocen los bordes del poliedro, la construcción de las facetas no es una tarea trivial. Todavía se conocen cierto número de algoritmos para la dimensión 3, pero también en el caso general.

Referencias

Marcel Berger , Geometry [ detalle de ediciones ], Prop. 11.1.8.4, volumen 3, pág. 26 en la edición de 1978.
(en) Charalambos D. Aliprantis y Kim C. Border , Infinite Dimensional Analysis: A Hitchhiker's Guide , Springer ,2007( leer en línea ) , pág. 185.
(en) Michael Ian Shamos , Geometría Computacional: PhD , Universidad de Yale ,1975
(en) Michael Ian Shamos y Dan Hoey , "Problemas más cercanos" , en Proceeding of 16th Annual IEEE Symposium on Foundations of Computer Science , Los Ángeles, IEEE Computer Society Press,1975( leer en línea ) , pág. 151-162.

Ver también

Enlace externo

(es) Algoritmos de casco convexo , subprograma Java 3D