Envolupant convexa

De Viquipèdia
Dreceres ràpides: navegació, cerca
Envolupant convexa d'un conjunt de 15 punts del pla

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  x_1, \, x_2, \, ..., x_k , la seva envolupant convexa C ve donada per l'expressió:

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.

Càlcul de l'envolupant convexa[modifica | modifica el codi]

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.

Algorismes per al càlcul de l'envolupant convexa en el pla[modifica | modifica el codi]

  • 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(n2).
  • 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.

Vegeu també[modifica | modifica el codi]

Referències[modifica | modifica el codi]