Algoritmo de Graham

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de julio de 2020; las comprobaciones requieren 5 ediciones .

El algoritmo de Graham es un algoritmo para construir un casco convexo en un espacio bidimensional. En este algoritmo, el problema del casco convexo se resuelve usando una pila formada por puntos candidatos. Todos los puntos del conjunto de entrada se colocan en la pila, y luego los puntos que no son vértices del casco convexo finalmente se eliminan. Al final del algoritmo, solo los vértices del caparazón permanecen en la pila en el orden en que se recorren en sentido contrario a las agujas del reloj.

Algoritmo

Los datos de entrada del procedimiento de Graham son el conjunto de puntos Q, donde . Llama a la función Top(S), que devuelve el punto en la parte superior de la pila S sin cambiar su contenido. Además, también se utiliza la función NextToTop(S), que devuelve el punto ubicado en la pila S, una posición por debajo del punto superior; la pila S no cambia. $|Q|\geqslant 3$

graham (q) 1) Sea un punto del conjunto Q con la coordenada mínima y o el más a la izquierda de tales puntos en presencia de coincidencias

p_{0}

2) Sean los puntos restantes del conjunto Q, ordenados en orden ascendente del ángulo polar,

<p_{1},p_{2},\ldots,p_{m}>

medido en sentido contrario a las agujas del reloj en relación con el punto (si los ángulos polares de varios puntos son iguales, entonces por la distancia al punto )

p_{0}

p_{0}

3) Empuje ( ,S)

p_{0}

4) Pulsar ( ,S)

p_{1}

5) para i = 2 a m do 6) mientras que el ángulo formado por los puntos NextToTop(S),Top(S) y , forman un giro no a la izquierda

Pi}

(al movernos por la línea quebrada formada por estos puntos, nos movemos en línea recta o hacia la derecha) 7) hacer Pop(S) 8) Pulsar ( ,S)

Pi}

9) devolver S

Para determinar si se forman tres puntos y un giro a la izquierda, puede usar una generalización del producto vectorial a un espacio bidimensional, es decir, la condición de giro a la izquierda se verá así: , donde $a$ $b$ $C$ $u_{x}v_{y}-u_{y}v_{x}\geqslant 0$ $u=\left\{b_{x}-a_{x},\;b_{y}-a_{y}\right\},v=\left\{c_{x}-b_{x} ,\;c_{y}-b_{y}\right\}$

Un ejemplo del funcionamiento del algoritmo de Graham.

Corrección de escaneo de Graham

Si el procedimiento de Graham procesa un conjunto de puntos Q, donde , entonces al final de este procedimiento, la pila S contendrá (de abajo hacia arriba) solo los vértices del caparazón CH(Q) en sentido antihorario. $|Q|\geqslant 3$

Prueba

Tras ejecutar la línea 2, tenemos a nuestra disposición una secuencia de puntos . Definamos un subconjunto de puntos para i = 2,3,…,m. El conjunto de puntos Q- forman aquellos que fueron eliminados debido a que su ángulo polar con respecto al punto p0 coincide con el ángulo polar de algún punto del conjunto . Estos puntos no pertenecen al casco convexo CH(Q), entonces CH( ) = CH(Q). Por lo tanto, basta con mostrar que, al final del procedimiento de Graham, la pila S consta de los vértices de la capa CH( ) en el sentido contrario a las agujas del reloj, si estos puntos se miran en la pila de abajo hacia arriba. Nótese que así como los puntos , , son vértices de la capa CH(Q), los puntos , , son vértices de la capa CH( ). $<p_{1},p_{2},\ldots,p_{m}>$ $Q_{i}=\izquierda\{p_{0},p_{1},\ldots,p_{i}\derecha\}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $Q_{m}$ $p_{0}$ $p_{1}$ $pm}$ $p_{0}$ $p_{1}$ $Pi}$ $Q_{yo}$

La prueba utiliza el ciclo invariante formulado a continuación. Al comienzo de cada iteración del ciclo for en las líneas 6-9, la pila S consta (de abajo hacia arriba) de solo los vértices de la capa CH( ) en el sentido contrario a las agujas del reloj. $Q_{{i-1}}$

Inicialización . La primera vez que se ejecuta la línea 6, se mantiene la invariante porque en ese punto la pila S consta de solo vértices = , y este conjunto de tres vértices forma su propio casco convexo. Además, si ve los puntos de abajo hacia arriba, se ubicarán en el sentido contrario a las agujas del reloj. $Q_{2}$ $Q_{{i-1}}$

Preservación _ Al ingresar una nueva iteración del bucle for, en la parte superior de la pila S está el punto , ubicado allí al final de la iteración anterior (o antes de la primera iteración, cuando i = 3). Sea el punto superior de la pila S después de la ejecución de las líneas 7-8 del ciclo while, pero antes de que el punto se coloque en la pila en la línea 9 . Sea también el punto ubicado en la pila S directamente debajo del punto . En el momento en que el punto está en la parte superior de la pila S y el punto aún no se ha agregado, la pila contiene los mismos puntos que después de la j-ésima iteración del ciclo for. Por lo tanto, de acuerdo con la invariante del bucle, en este punto, la pila S contiene solo CH( ) en el sentido de las agujas del reloj, visto de abajo hacia arriba. El ángulo polar del punto relativo al punto es mayor que el ángulo polar del punto , y dado que el ángulo gira hacia la izquierda (de lo contrario, el punto se eliminaría de la pila), después de agregar el punto a la pila S (antes solo había vértices CH( )) contendrá vértices CH( ). Al mismo tiempo, se ordenarán en sentido contrario a las agujas del reloj, si se ven de abajo hacia arriba. $p_{{i-1}}$ $p_{j}$ $Pi}$ $paquete}$ $p_{j}$ $p_{j}$ $Pi}$ $Q_{j}$ $Pi}$ $p_{0}$ $p_{j}$ $paquete}$ $p_{j}$ $Pi}$ $p_{j}$ $Pi}$ $Q_{j}$ $Q_{j}\taza \izquierda\{p_{i}\derecha\}$

Demostremos que el conjunto de vértices CH( ) coincide con el conjunto de puntos CH( ). Considere un punto arbitrario extraído de la pila durante la i-ésima iteración del bucle for, y sea el punto ubicado en la pila S inmediatamente debajo del punto anterior a la última extracción de la pila (este punto pr puede ser el punto ). El ángulo no gira hacia la izquierda y el ángulo polar del punto relativo al punto es mayor que el ángulo polar del punto . Como el punto está dentro del triángulo formado por otros tres puntos del conjunto , no puede ser el vértice de CH( ). Como no es un vértice de CH( ), entonces CH( - { }) = CH( ). Sea el conjunto de puntos tomados de la pila durante la ejecución de la i-ésima iteración del bucle for. La igualdad CH( - ) = CH( ) es verdadera. Sin embargo — = { }, por lo que concluimos que CH( { }) = CH( — ) = CH( ). $Q_{j}\taza \izquierda\{p_{i}\derecha\}$ $Q_{yo}$ $p_{t}$ $p_{r}$ $p_{t}$ $p_{j}$ $p_{r}$ $p_{t}$ $Pi}$ $p_{t}$ $p_{0}$ $p_{r}$ $p_{t}$ $Q_{yo}$ $Q_{yo}$ $p_{t}$ $Q_{yo}$ $Q_{yo}$ $p_{t}$ $Q_{yo}$ $Pi}$ $Q_{yo}$ $Pi}$ $Q_{yo}$ $Q_{yo}$ $Pi}$ $Q_{yo}$ $\taza$ $Pi}$ $Q_{j}$ $\taza$ $Pi}$ $Q_{yo}$ $Pi}$ $Q_{yo}$

Inmediatamente después de sacar el punto de la pila S , contiene solo los vértices CH( ) en el orden en que se recorren en sentido contrario a las agujas del reloj, si los observa en la pila de abajo hacia arriba. El aumento subsiguiente en uno del valor de i conducirá a la preservación del bucle invariante en la siguiente iteración. $Pi}$ $Q_{yo}$

Finalización . Al final del ciclo, se satisface la igualdad i = m + 1, por lo que del invariante del ciclo se deduce que la pila S consta solo de los vértices de CH( ), es decir, de los vértices de CH(Q). Estos vértices están en orden transversal en sentido contrario a las agujas del reloj cuando se ven en la pila de abajo hacia arriba. $Q_{m}$

Horario de apertura

El tiempo de ejecución del procedimiento Graham es , donde . Como puede ver fácilmente, el ciclo while tomará el tiempo O( ). Si bien clasificar los ángulos polares llevará tiempo, de ahí el comportamiento asintótico general del procedimiento de Graham. $O(N\log N)$ $N=|Q|$ $norte$ $O(N\log N)$

Véase también

Algoritmo de Jarvis
algoritmo de Chan
Algoritmo de caparazón rápido
Algoritmo de cadena monotónica de Andrew

Literatura

T. Kormen, C. Leizerson, R. Rivest, K. Stein. Algoritmos. Construcción y Análisis = Introducción a los Algoritmos. - 2ª ed. - "Williams", 2005.