Envolupant convexa

En matemàtiques es defineix l'envolupant convexa d'un conjunt de punts X de dimensió n com la intersecció de tots els conjunts convexos que contenen X.^[1]

Donats k punts ${\displaystyle x_{1},\,x_{2},\,...,x_{k}}$, la seva envolupant convexa C ve donada per l'expressió:

${\displaystyle 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 _{i}=1\right\}}$

En el cas particular de punts en un pla, si no tots els punts estan alineats, llavors la seva envolupant convexa correspon a un polígon convex els vèrtexs del qual són alguns dels punts del conjunt inicial.

Una forma intuïtiva de veure l'envolupant convexa d'un conjunt de punts al pla és imaginar una banda elàstica estirada que els tanca a tots. Quan s'alliberi la banda elàstica, aquesta prendrà la forma de l'envolupant convexa.

En geometria computacional existeixen nombrosos algorismes per calcular l'envolupant convexa d'un conjunt finit de punts, amb diversos graus de complexitat computacional. La complexitat de l'algorisme de resolució se sol estimar en funció del nombre n de punts d'entrada i el nombre h de punts de la corresponent envolupant convexa.

• Jarvis march o gift wrapping algorithm. Proposat per R. A. Jarvis el 1973. És un dels més simples i posseeix una complexitat computacional O(nh). En el pitjor dels casos la seva complexitat serà O(n²).
• Mètode de Graham. Publicat el 1972, és molt més eficient i posseeix una complexitat computacional O(n log n). Si els punts es troben ordenats per una de les coordenades o per l'angle a un vector fix llavors la complexitat és O(n).
• Divide and conquer. Un altre algorisme de complexitat O(n log n) publicat el 1977 per Franco P. Preparata i Hong. També és aplicable al cas tridimensional.

• Determinants de Cayley-Menger
• Símplex