Algoritmo de envoltura de regalos

En geometría computacional, el algoritmo de envoltura de regalos es un procedimiento ideado para calcular la envolvente convexa de un conjunto de puntos dado.

Caso plano

En el caso bidimensional, el algoritmo también se conoce como marcha de Jarvis, en referencia a R. A. Jarvis, quien lo publicó en 1973. Tiene complejidad temporal O(nh), donde n es el número de puntos y h es el número de puntos en la envolvente convexa. Su rendimiento en la práctica, comparado con otros algoritmos de envolvente convexa, es favorable cuando n es pequeño o se espera que h sea muy pequeño con respecto a n. En casos generales, muchos otros algoritmos lo superan en rendimiento (véase algoritmos de envolvente convexa).

Algoritmo

Para simplificar, la descripción que sigue asume que los puntos se sitúan en posición general, es decir, que no hay tres puntos colineales (que pertenezcan a la misma recta). El algoritmo puede modificarse fácilmente para abordar la colinealidad, incluyendo la decisión de si debe reportar solo los puntos extremos (vértices de la envolvente convexa) o todos los puntos que se encuentran en la envolvente convexa. Asimismo, la implementación completa debe definir cómo manejar los casos degenerados, cuando la envolvente convexa tiene solo 1 o 2 vértices, así como los problemas relacionados con la limitación de cifras significativas, tanto en los cálculos computacionales como en los datos de entrada.

El algoritmo de envoltura de regalos comienza con i=0 y un punto p₀ conocido por estar en la envolvente convexa, por ejemplo, el punto más a la izquierda, y selecciona el punto p_i+1 de tal manera que todos los puntos estén a la derecha de la línea p_i p_i+1. Este punto se puede encontrar en O(n) tiempo comparando los ángulos polares de todos los puntos con respecto al punto p_i tomado como centro de coordenadas polares. Haciendo i=i+1, y repitiendo hasta llegar a p_h=p₀ nuevamente, se obtiene la envolvente convexa en h pasos. En dos dimensiones, el algoritmo de envoltura de regalos es similar al proceso de enrollar una cuerda (o papel de regalo) alrededor del conjunto de puntos.

El enfoque puede extenderse a dimensiones superiores.

Pseudocódigo

algorithm jarvis(S) is
    // S es el conjunto de puntos
    // P será el conjunto de puntos que forman la envolvente convexa. El tamaño final del conjunto es i.
    pointOnHull := leftmost point in S // que está garantizado que formará parte de la envolvente CH(S)
    i := 0
    repeat
        P[i] := pointOnHull
        endpoint := S[0]      // punto final inicial para una arista candidata a estar en la envolvente
        for j from 0 to |S| do
            // endpoint == pointOnHull es un caso raro y solo puede ocurrir cuando j == 1 y aún no se ha establecido un mejor endpoint para el bucle.
            if (endpoint == pointOnHull) or (S[j] is on left of line from P[i] to endpoint) then
                endpoint := S[j]   // giro a la izquierda mayor encontrado, actualizar el punto final.
        i := i + 1
        pointOnHull := endpoint
    until endpoint == P[0]      // envoltura hasta el primer punto de la envolvente

El código completo se puede en contrar en OpenGenus IQ y en GeeksforGeeks.

Complejidad

El bucle interno comprueba cada punto del conjunto S, y el bucle externo se repite para cada punto del contorno. Por lo tanto, el tiempo total de ejecución es ${\displaystyle O(nh)}$. El tiempo de ejecución depende del tamaño de la salida, por lo que la marcha de Jarvis es un algoritmo sensible a la salida.

Sin embargo, dado que el tiempo de ejecución depende linealmente del número de vértices de la envolvente convexa, solo es más rápido que algoritmos como el método de Graham (${\displaystyle O(n\log n)}$) cuando el número de vértices de la envolvente convexa es menor que logₙ. El algoritmo de Chan, otro algoritmo de envolvente convexa, combina la dependencia logarítmica del método de Graham con la sensibilidad de salida del algoritmo de envoltura de regalos, logrando un tiempo de ejecución asintótico (${\displaystyle O(n\log h)}$) que mejora tanto el método de Graham como el algoritmo de envoltura de regalos.

Véase también

• Algoritmos de envolvente convexa

Referencias

Bibliografía