Anar al contingut

Envolvent convexa

De L'Enciclopèdia, la wikipedia en valencià
Envolvent convexa
Envoltura convexa d'un conjunt de 8 punts en el pla.

En matemàtiques es definix la envolvent 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.[1]

Donats k punts x1,x2,...,xk el seu envolvent convexa C ve donada per l'expressió:

C(X)={∑i=1kαixi | xi∈X,αi∈ℝ,αi≥0,∑i=1kαi=1}

En el cas particular de punts en un pla, si no tots els punts estan alineats, llavors el seu envolvent 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 envolvent 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 envolvent convexa.

Alternativament

L'unió de totes les combinacions convexas de conjunts finitos de punts de A⊂Rn es denomina càpsula convexa de A.[2]

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⊂Rn que tenen a lo més n+1 punts.[2]

Càlcul de la envolvent convexa

En geometria computacional existixen numerosos algoritmes per a calcular la envolvent convexa d'un conjunt finit 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 envolvent convexa.

Algoritmes per al càlcul de la envolvent 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(n2).
  • 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.[3]

Referències

  1. ↑ envolvent convexa en MathWorld.
  2. ↑ 2,0 2,1 Boss, V. (2011). Àlgebra llineal, Moscou: Editorial URSS. ISBN 978-5-396-00066-7.
  3. ↑ Preparata, Franco P.; Hong, S.J.(1977).«Convex hulls of finite sets of points in two and three dimensions».Communications of the ACM.20(2)doi:10.1145/359423.359430.

Vore també