Envoltura convexa

De Wikipedia, la enciclopedia libre

Envoltura convexa de un conjunto de 15 puntos en el plano

En matemática se define la envoltura convexa de un conjunto de puntos X de dimensión n como la intersección de todos los conjuntos convexos que contienen a X.^[1]

Dados k puntos $x_1,\, x_2,\, ...,x_k$ su envoltura convexa C viene dada por la expresión:

$C(X) =\left\{\sum_{i=1}^k \alpha_i x_i \ \Bigg | \ x_i\in X, \, \alpha_i\in \mathbb{R}, \, \alpha_i \geq 0 \, \sum_{i=1}^k \alpha_k=1\right\}.$

En el caso particular de puntos en un plano, si no todos los puntos están alineados, entonces su envoltura 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 envoltura 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 envoltura convexa.

[editar] Cálculo de la envoltura convexa

En geometría computacional existen numerosos algoritmos para calcular la envoltura 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 de el número n de puntos de entrada, y el número h de puntos de la correspondiente envoltura convexa.

[editar] Algoritmos para el cálculo de la envoltura convexa en el plano

Jarvis march o gift wrapping algorithm. 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(n²).

Graham scan. Publicado en 1972, es mucho más eficiente y posee una complejidad computacional O(n log n). Si los puntos se encuentran ordenados por una de las coordenadas o por el ángulo a un vector fijo entonces la complejidad es O(n).

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.

[editar] Referencias

↑ Mathworld

El contenido de esta página es un esbozo sobre matemática. Ampliándolo ayudarás a mejorar Wikipedia.
Puedes ayudarte con las wikipedias en otras lenguas.