En matemáticas se define la envolvente convexa, envoltura convexa o cápsula convexa de un conjunto de puntos X de dimensión n como la intersección de todos los conjuntos convexos que contienen a X.
Dados k puntos su envolvente convexa C viene dada por la expresión:
En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envolvente convexa corresponde a un polígono convexo cuyos vértices son algunos de los puntos del conjunto inicial de puntos.
Una forma intuitiva de ver la envolvente convexa de un conjunto de puntos en el plano, es imaginar una banda elástica estirada que los encierra a todos. Cuando se libere la banda elástica tomará la forma de la envolvente convexa.
Definición alternativa
La envoltura convexa de un conjunto puede definirse equivalentemente como el conjunto de todas las combinaciones convexas de subconjuntos finitos de . Es decir,
Teorema de Carathéodory
El teorema de Carathéodory establece que, en , la envoltura convexa de un conjunto coincide con la unión de todas las combinaciones convexas de subconjuntos de con a lo sumo puntos. Es decir, todo punto de la envoltura convexa puede expresarse como combinación convexa de puntos (o menos) del conjunto original.
Cálculo de la envolvente convexa
En geometría computacional existen numerosos algoritmos para calcular la envolvente convexa de un conjunto finito de puntos, con diversos grados de complejidad computacional. La complejidad del algoritmo de resolución se suele estimar en función del número n de puntos de entrada, y el número h de puntos de la correspondiente envolvente convexa.
Algoritmos para el cálculo de la envolvente convexa en el plano
Marcha de Jarvis o envoltura de regalos: Propuesto por R. A. Jarvis en 1973. Es uno de los más simples y posee una complejidad computacional O(nh). En el peor de los casos su complejidad será O(n2). Método de Graham: Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(n log n). Si los puntos se encuentran pre-ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(n). Quickhull: Un método recursivo creado de forma independiente en 1977 por W. Eddy y A. Bykat. Tiene una complejidad esperada O(n log n), pero que puede degenerar a O(n^2) en el peor caso. Divide y vencerás (Divide and conquer): Otro algoritmo de complejidad O(n log n) publicado en 1977 por Franco P. Preparata y Hong. También es aplicable al caso tridimensional.
Referencias
Véase también Algoritmos de envolvente convexa Convexidad Envolvente ortogonalmente convexa
Categoría:Álgebra lineal Categoría:Geometría convexa Categoría:Algoritmos geométricos Categoría:Procesamiento en geometría Categoría:Geometría computacional Categoría:Operadores de cierre