Envolvente convexa

Archiu:Extreme points.svg

Envolvente convexa

Archiu:ConvexClosure.svg

Envoltura convexa d'un conjunt de 8 punts en el pla.

En matemàtiques es definix la envolvente convexa, envoltura convexa o càpsula convexa d'un conjunt de punts X de dimensió n com l'intersecció de tots els conjunts convexos que contenen a X.

Donats k punts $x_1,x_2,\mathrm{...},x_k$ el seu envolvente convexa C ve donada per l'expressió:

$C(X)=\left\{\sum _{i=1}^k{\alpha }_i{x}_i\right|x_i\in X,{\alpha }_i\in ℝ,{\alpha }_i\ge 0,\sum _{i=1}^k{\alpha }_i=1\}$

En el cas particular de punts en un pla, si no tots els punts estan alineats, llavors el seu envolvente convexa correspon a un polígon convexo els vèrtiços del qual són alguns dels punts del conjunt inicial de punts.

Una forma intuïtiva de vore la envolvente convexa d'un conjunt de punts en el pla, és imaginar una banda elàstica estirada que els tanca a tots. Quan es llibere la banda elàstica prendrà la forma de la envolvente convexa.

Alternativament

L'unió de totes les combinacions convexas de conjunts finitos de punts de $A\subset R^n$ es denomina càpsula convexa de $A$.

Teorema de Carathéodory

La càpsula convexa d'un conjunt coincidix en l'unió de totes les combinacions convexas possibles de subconjunts finitos del conjunt $A\subset R^n$ que tenen a lo més $n+1$ punts.

Càlcul de la envolvente convexa

En geometria computacional existixen numerosos algoritmes per a calcular la envolvente convexa d'un conjunt finito de punts, en diversos graus de complexitat computacional. La complexitat de l'algoritme de resolució se sol estimar en funció del número n de punts d'entrada, i el número h de punts de la corresponent envolvente convexa.

Algoritmes per al càlcul de la envolvente convexa en el pla

• Jarvis march o gift wrapping algorithm: Propost per R. A. Jarvis en 1973. És un dels més simples i posseïx una complexitat computacional O(nh). En el pijor dels casos la seua complexitat serà O(n²).
• Método de Graham: Publicat en 1972, és molt més eficient i posseïx una complexitat computacional O(n log n). Si els punts es troben pre-ordenats per una de les coordenades o per l'àngul a un vector fix llavors la complexitat és O(n).
• Quickhull: Un método recursivo creat de forma independent en 1977 per W. Eddy i A. Bykat. Té una complexitat esperada O(n log n), pero que pot degenerar a O(n^2) en el pijor cas.
• Dividix i venceràs (Dividix and conquer): Un atre algoritme de complexitat O(n log n) publicat en 1977 per Franco P. Preparata i Hong. També és aplicable al cas tridimensional.

Vore també

• Convexidad
• Envolvente ortogonalment convexa