Método de Graham

Método de Graham aplicat pas a pas per a calcular la envolvente convexa d'un conjunt de punts

El método de Graham (Graham scan) és un método de càlcul computacional de l'envolvente convexa d'un conjunt finito de punts en el pla, de complexitat O(nlogn). El nom fa honor a Ronald Graham, qui va publicar l'algoritme en 1972. L'algoritme calcula tots els vèrtiços de la envolvente convexa ordenats a lo llarc de la frontera. Pot ser fàcilment modificat per a calcular els punts que, sense ser vèrtiços, pertanyen a dita envolvente.

Algoritme

Com es pot vore, el gir entre els vectores PA i AB és contrari les agulles del rejoj, pero no ho és el gir entre BC i CD. L'algoritme detecta esta situació i descarta els segments que duen a un gir dextrógiro.

Com es pot vore, el gir entre els vectores PA i AB és contrari les agulles del rejoj, pero no ho és el gir entre BC i CD. L'algoritme detecta esta situació i descarta els segments que duen a un gir dextrógiro.

El primer pas d'este algoritme consistix en trobar el punt en la menor coordenada ordenada (menor coordenada en l'eix i). Si hi ha més d'un punt que complixca esta condició, es tria el punt en menor coordenada en l'eix x. A este punt li'l nomena per la lletra P. Este pas és de complexitat O(n), a on n és el número de punts del problema.

Despuix, el conjunt de punts deu ser ordenat en orde creixent d'àngul comprés entre el segment que els unix en el punt P i l'eix d'abscisses. Per a això es pot utilisar qualsevol algoritme d'ordenament. Per a agilitar el procés, es pot ometre el càlcul de l'àngul ya que és suficient en trobar el seu cotangente.

L'algoritme continua tractant seqüència de punts ordenats segons l'àngul creixent. Per a cada punt es calcula si el moviment des dels dos anteriors és un "gir a dreta" o un "gir a esquerra". Si el moviment és dextrógiro, indica que el segon punt de la terna no és part de la envolvente convexa i deu deixar de considerar-se en els càlculs i prendre el següent. Quan es troba un gir a esquerra, l'algoritme passa a calcular el següent punt. En cas que existixquen punts alineats pertanyents a la envolvente, els centrals poden ser descartats o considerats com a part de la mateixa.

No és necessari calcular l'àngul entre tres punts per a saber si és un gir a dreta o a esquerra, puix pot conéixer-se eixa senya en una sola operació aritmètica. Per a tres punts $(x_1,y_1)$, $(x_2,y_2)$ i $(x_3,y_3)$, es pot calcular el producte vectorial dels dos vectores definits per les coordenades $(x_1,y_1)$, $(x_2,y_2)$ i $(x_1,y_1)$, $(x_3,y_3)$, de tal manera que el resultat s'obté en l'equació $(x_2-x_1)(y_3-y_1)-(y_2-y_1)(x_3-x_1)$. Si el resultat és 0, els punts està alineats, si és positiu, el gir és a esquerres i, si és negatiu, el gir és a dreta.

Finalment, en este procés es torna al punt P de partida, moment en el que l'algoritme està completat i solament queden els punts pertanyents a la envolvente convexa correctament ordenats.

Complexitat

L'ordenament dels punts té una complexitat O(nlogn). Encara que semble que la complexitat del procés és O(n²), puix per a cada punt torna arrere per a comprovar si algun de les coordenades anteriors du a un gir dextrógiro, realment és O(n) ya que cada punt es considera com a molt en dos ocasions en cada sentit. Cada punt pot aparéixer solament una volta com $(x_3,y_3)$ en un gir a esquerres ya que l'algoritme alvança al següent punt en eixe cas i com a punt $(x_2,y_2)$ en un gir a dretes, ya que en eixe cas, el punt és eliminat. La complexitat total és per tant O(nlogn) ya que el temps per a ordenar els punts domina sobre el temps necessari per a calcular la envolvente.

Notes

La mateixa idea bàsica funciona si els punts estan ordenats segons l'eix ordenat en lloc de l'àngul, i la envolvente es calcula en dos passos, generant la part superior i la part inferior de la mateixa.

La tècnica d'apilar senyes usada en el método de Graham és molt similar a l'utilisat en el problema de càlcul del valor menor més propenc, el qual pot ser usat també per a calcular eficientemente envolventes convexas d'una série de punts.