Algoritmo de Chan

Descripción general

Una sola pasada del algoritmo requiere un parámetro ${\displaystyle m}$ que se encuentra entre 0 y ${\displaystyle n}$ (número de puntos del conjunto ${\displaystyle P}$). Idealmente, ${\displaystyle m=h}$, pero ${\displaystyle h}$, el número de vértices en la envolvente convexa de salida, se desconoce al inicio. Se realizan múltiples pasadas con valores crecientes de ${\displaystyle m}$, que finalizan cuando ${\displaystyle m\geq h}$ alcanza un valor determinado. Véase más abajo la elección del parámetro ${\displaystyle m}$.

El algoritmo comienza dividiendo arbitrariamente el conjunto de puntos ${\displaystyle P}$ en ${\displaystyle K=\lceil n/m\rceil }$ subconjuntos ${\displaystyle (Q_{k})_{k=1,2,...K}}$ con un máximo de ${\displaystyle m}$ puntos cada uno; nótese que ${\displaystyle K=O(n/m)}$.

Para cada subconjunto ${\displaystyle Q_{k}}$, calcula la envolvente convexa, ${\displaystyle C_{k}}$, utilizando un algoritmo ${\displaystyle O(p\log p)}$ (por ejemplo, el método de Graham), donde ${\displaystyle p}$ es el número de puntos en el subconjunto. Dado que hay ${\displaystyle K}$ subconjuntos de ${\displaystyle O(m)}$ puntos cada uno, esta fase requiere un tiempo ${\displaystyle K\cdot O(m\log m)=O(n\log m)}$.

Durante la segunda fase, se ejecuta la marcha de Jarvis, utilizando las (mini) envolventes convexas precalculadas, ${\displaystyle (C_{k})_{k=1,2,...K}}$. En cada paso de este algoritmo de marcha de Jarvis, se tiene un punto ${\displaystyle p_{i}}$ en la envolvente convexa (al principio, ${\displaystyle p_{i}}$ puede ser el punto en ${\displaystyle P}$ con la coordenada y más baja, que está garantizado que está en la envolvente convexa de ${\displaystyle P}$), y se necesita encontrar un punto ${\displaystyle p_{i+1}=f(p_{i},P)}$ tal que todos los demás puntos de ${\displaystyle P}$ estén a la derecha de la línea ${\displaystyle p_{i}p_{i+1}}$, donde la notación ${\displaystyle p_{i+1}=f(p_{i},P)}$ simplemente significa que el siguiente punto, es decir, ${\displaystyle p_{i+1}}$, se determina como una función de ${\displaystyle p_{i}}$ y ${\displaystyle P}$. Se conoce la envolvente convexa del conjunto ${\displaystyle Q_{k}}$, ${\displaystyle C_{k}}$, y contiene como máximo ${\displaystyle m}$ puntos (ordenados en sentido horario o antihorario), lo que permite calcular ${\displaystyle f(p_{i},Q_{k})}$ en tiempo ${\displaystyle O(\log m)}$ mediante búsqueda binaria. Por lo tanto, el cálculo de ${\displaystyle f(p_{i},Q_{k})}$ para todos los subconjuntos ${\displaystyle K}$ se puede realizar en tiempo ${\displaystyle O(K\log m)}$. Luego, se puede determinar ${\displaystyle f(p_{i},P)}$ utilizando la misma técnica que se usa normalmente en la marcha de Jarvis, pero considerando solo los puntos ${\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}$ (es decir, los puntos en las mini envolventes convexas) en lugar de todo el conjunto ${\displaystyle P}$. Para esos puntos, una iteración de la marcha de Jarvis es ${\displaystyle O(K)}$, lo cual es insignificante comparado con el cálculo para todos los subconjuntos. La marcha de Jarvis finaliza cuando el proceso se ha repetido ${\displaystyle O(h)}$ veces (porque, según su funcionamiento, tras como máximo ${\displaystyle h}$ iteraciones de su bucle más externo, donde ${\displaystyle h}$ es el número de puntos en la envolvente convexa de ${\displaystyle P}$, se debe haber encontrado dicha envolvente). Por lo tanto, la segunda fase requiere un tiempo de ${\displaystyle O(Kh\log m)}$, equivalente a un tiempo de ${\displaystyle O(n\log h)}$ si ${\displaystyle m}$ está cerca de ${\displaystyle h}$ (véase más abajo la descripción de una estrategia para elegir ${\displaystyle m}$ de forma que esto ocurra).

Al ejecutar las dos fases descritas anteriormente, la envolvente convexa de ${\displaystyle n}$ puntos se calcula en tiempo ${\displaystyle O(n\log h)}$.

Elección del parámetro m

Si se elige un valor arbitrario para ${\displaystyle m}$, puede ocurrir que ${\displaystyle m<h}$. En ese caso, después de ${\displaystyle m}$ pasos en la segunda fase, se interrumpe la marcha de Jarvis, ya que ejecutarla hasta el final llevaría demasiado tiempo.

En ese momento, se habrá consumido un tiempo ${\displaystyle O(n\log m)}$ y la envolvente convexa no se habrá calculado.

La idea es realizar múltiples pasadas del algoritmo con valores crecientes de ${\displaystyle m}$; cada pasada finaliza (con éxito o sin éxito) en tiempo ${\displaystyle O(n\log m)}$. Si ${\displaystyle m}$ aumenta demasiado lentamente entre pasadas, el número de iteraciones puede ser grande. Por otro lado, si aumenta demasiado rápido, el primer ${\displaystyle m}$ para el cual el algoritmo finaliza con éxito puede ser mucho mayor que ${\displaystyle h}$, y producir una complejidad ${\displaystyle O(n\log m)>O(n\log h)}$.

En tres dimensiones

Para generalizar esta construcción al caso tridimensional, se debe utilizar el algoritmo ${\displaystyle O(n\log n)}$ de Preparata y Hong para calcular la envolvente convexa tridimensional en lugar del método de Graham, y una versión tridimensional de la marcha de Jarvis. La complejidad temporal permanece como ${\displaystyle O(n\log h)}$.

Pseudocódigo

En el siguiente pseudocódigo, el texto entre paréntesis y en cursiva son comentarios. Para comprender completamente el siguiente pseudocódigo, se recomienda que el lector esté familiarizado con los algoritmos del método de Graham y de la marcha de Jarvis para calcular la envolvente convexa, ${\displaystyle C}$, de un conjunto de puntos ${\displaystyle P}$.

Entrada: Establecer ${\displaystyle P}$ con ${\displaystyle n}$ puntos.

Salida: Establece ${\displaystyle C}$ con ${\displaystyle h}$ puntos, la envolvente convexa de ${\displaystyle P}$.

(Seleccionar un punto de ${\displaystyle P}$ que esté garantizado que pertenece a ${\displaystyle C}$: por ejemplo, el punto con la coordenada y más baja.)

(Esta operación toma ${\displaystyle {\mathcal {O}}(n)}$ tiempo: por ejemplo, se puede simplemente iterar a través de ${\displaystyle P}$.)

${\displaystyle p_{1}:=PICK\_START(P)}$

(${\displaystyle p_{0}}$ se utiliza en la marcha de Jarvis de este algoritmo de Chan,

para calcular el segundo punto, ${\displaystyle p_{2}}$, en la envolvente convexa de ${\displaystyle P}$.)

(Nota: ${\displaystyle p_{0}}$ no es un punto de ${\displaystyle P}$.)

(Para más información, consulte los comentarios junto a la parte correspondiente del algoritmo de Chan.)

${\displaystyle p_{0}:=(-\infty ,0)}$

(Nota: ${\displaystyle h}$, el número de puntos en la envolvente convexa final de ${\displaystyle P}$, es desconocido.

(Estas son las iteraciones necesarias para descubrir el valor de ${\displaystyle m}$, que es una estimación de ${\displaystyle h}$.)

(${\displaystyle h\leq m}$ es necesario para que este algoritmo de Chan encuentre la envolvente convexa de ${\displaystyle P}$.)

(Más específicamente, queremos ${\displaystyle h\leq m\leq h^{2}}$, para no realizar demasiadas iteraciones innecesarias y para que la complejidad temporal de este algoritmo de Chan sea ${\displaystyle {\mathcal {O}}(n\log h)}$.)

(Como se explicó anteriormente en este artículo, se utiliza una estrategia en la que se requieren como máximo ${\displaystyle \log \log n}$ iteraciones para encontrar ${\displaystyle m}$.)

(Nota: el ${\displaystyle m}$ final puede no ser igual a ${\displaystyle h}$, pero nunca es menor que ${\displaystyle h}$ ni mayor que ${\displaystyle h^{2}}$.)

(Sin embargo, este algoritmo de Chan se detiene una vez que se realizan ${\displaystyle h}$ iteraciones del bucle más externo,

es decir, incluso si ${\displaystyle m\neq h}$, no realiza ${\displaystyle m}$ iteraciones del bucle más externo.)

(Para más información, consulte la parte de la marcha de Jarvis de este algoritmo a continuación, donde se devuelve ${\displaystyle C}$ si ${\displaystyle p_{i+1}==p_{1}}$.)

para ${\displaystyle 1\leq t\leq \log \log n}$ hacer

(Establecer el parámetro ${\displaystyle m}$ para la iteración actual. Se utiliza un "esquema de elevación al cuadrado" como se describe anteriormente en este artículo.

Existen otros esquemas: por ejemplo, el "esquema de duplicación", donde ${\displaystyle m=2^{t}}$, para ${\displaystyle t=1,\dots ,\left\lceil \log h\right\rceil }$.

Si se utiliza el "esquema de duplicación", la complejidad temporal resultante de este algoritmo de Chan es ${\displaystyle {\mathcal {O}}(n\log ^{2}h)}$.

${\displaystyle m:=2^{2^{t}}}$

(Inicializa una lista (o arreglo) vacía para almacenar los puntos de la envolvente convexa de ${\displaystyle P}$, a medida que se encuentran.)

${\displaystyle C:=()}$

${\displaystyle ADD(C,p_{1})}$

(Divide arbitrariamente el conjunto de puntos ${\displaystyle P}$ en ${\displaystyle K=\left\lceil {\frac {n}{m}}\right\rceil }$ subconjuntos de aproximadamente ${\displaystyle m}$ elementos cada uno.)

${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}:=SPLIT(P,m)}$

(Calcula la envolvente convexa de todos los ${\displaystyle K}$ subconjuntos de puntos, ${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$.)

(Tarda Tiempo ${\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}$.

Si ${\displaystyle m\leq h^{2}}$, entonces la complejidad temporal es ${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$.'

para ${\displaystyle 1\leq k\leq K}$ hacer

(Calcular la envolvente convexa del subconjunto ${\displaystyle k}$, ${\displaystyle Q_{k}}$, usando el escaneo de Graham, que toma ${\displaystyle {\mathcal {O}}(m\log m)}$ tiempo.'

(${\displaystyle C_{k}}$ es la envolvente convexa del subconjunto de puntos ${\displaystyle Q_{k}}$.'

${\displaystyle C_{k}:=GRAHAM\_SCAN(Q_{k})}$

(En este punto, se han calculado las envolventes convexas ${\displaystyle C_{1},C_{2},\dots ,C_{K}}$ de los subconjuntos de puntos ${\displaystyle Q_{1},Q_{2},\dots ,Q_{K}}$ respectivamente.)

(Ahora, use una versión modificada del algoritmo marcha de Jarvis para calcular la envolvente convexa de ${\displaystyle P}$.)

(La marcha de Jarvis se ejecuta en ${\displaystyle {\mathcal {O}}(nh)}$ tiempo, donde ${\displaystyle n}$ es el número de puntos de entrada y ${\displaystyle h}$ es el número de puntos en la envolvente convexa.)

(Dado que la marcha de Jarvis es un algoritmo sensible a la salida, su tiempo de ejecución depende del tamaño de la envolvente convexa, ${\displaystyle h}$.)

(En la práctica, esto significa que la marcha de Jarvis realiza ${\displaystyle h}$ iteraciones de su bucle más externo.)

En cada una de las En estas iteraciones, realiza como máximo ${\displaystyle n}$ iteraciones de su bucle más interno.

(Queremos ${\displaystyle h\leq m\leq h^{2}}$, por lo que no queremos realizar más de ${\displaystyle m}$ iteraciones en el siguiente bucle externo.)

(Si el ${\displaystyle m}$ actual es menor que ${\displaystyle h}$, es decir, ${\displaystyle m<h}$, no se puede encontrar la envolvente convexa de ${\displaystyle P}$.)

(En esta versión modificada de la marcha de Jarvis, realizamos una operación dentro del bucle más interno que tarda ${\displaystyle {\mathcal {O}}(\log m)}$ tiempo.

Por lo tanto, la complejidad temporal total de esta versión modificada es

${\displaystyle {\mathcal {O}}(mK\log m)={\mathcal {O}}(m\left\lceil {\frac {n}{m}}\right\rceil \log m)={\mathcal {O}}(n\log m)={\mathcal {O}}(n\log 2^{2^{t}})={\mathcal {O}}(n2^{t}).}$

Si ${\displaystyle m\leq h^{2}}$, entonces la complejidad temporal es ${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$.'

para ${\displaystyle 1\leq i\leq m}$ hacer

(Nota: aquí, ya se conoce un punto en la envolvente convexa de ${\displaystyle P}$, que es ${\displaystyle p_{1}}$.)

(En este bucle para interno, se calculan ${\displaystyle K}$ posibles puntos siguientes que se encuentran en la envolvente convexa de ${\displaystyle P}$, ${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$.)

(Cada uno de estos ${\displaystyle K}$ posibles puntos siguientes proviene de un ${\displaystyle C_{k}}$ diferente):

es decir, ${\displaystyle q_{i,k}}$ es un posible punto siguiente en la envolvente convexa de ${\displaystyle P}$, que forma parte de la envolvente convexa de ${\displaystyle C_{k}}$.)

(Nota: ${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$ depende de ${\displaystyle i}$: es decir, para cada En cada iteración ${\displaystyle i}$, existen ${\displaystyle K}$ posibles puntos siguientes que pueden estar en la envolvente convexa de ${\displaystyle P}$.

(Nota: en cada iteración ${\displaystyle i}$, solo uno de los puntos ${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$ se añade a la envolvente convexa de ${\displaystyle P}$).

para ${\displaystyle 1\leq k\leq K}$ hacer

(${\displaystyle JARVIS\_BINARY\_SEARCH}$ encuentra el punto ${\displaystyle d\in C_{k}}$ tal que el ángulo ${\displaystyle \measuredangle p_{i-1}p_{i}d}$ se maximiza

donde ${\displaystyle \measuredangle p_{i-1}p_{i}d}$ es el ángulo entre los vectores ${\displaystyle {\overrightarrow {p_{i}p_{i-1}}}}$ y ${\displaystyle {\overrightarrow {p_{i}d}}}$. Este ángulo ${\displaystyle d}$ se almacena en ${\displaystyle q_{i,k}}$.

(Los ángulos no necesitan calcularse directamente: se puede usar una prueba de orientación).

(${\displaystyle JARVIS\_BINARY\_SEARCH}$ se puede realizar en tiempo ${\displaystyle {\mathcal {O}}(\log m)}$.)

(Nota: en la iteración ${\displaystyle i=1}$, ${\displaystyle p_{i-1}=p_{0}=(-\infty ,0)}$ y ${\displaystyle p_{1}}$ se conoce y es un punto en la envolvente convexa de ${\displaystyle P}$:

en este caso, es el punto de ${\displaystyle P}$ con la coordenada y más baja.'

${\displaystyle q_{i,k}:=JARVIS\_BINARY\_SEARCH(p_{i-1},p_{i},C_{k})}$

(Elegir el punto ${\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}$ que maximiza el ángulo ${\displaystyle \measuredangle p_{i-1}p_{i}z}$ para que sea el siguiente punto en la envolvente convexa de ${\displaystyle P}$).

${\displaystyle p_{i+1}:=JARVIS\_NEXT\_CH\_POINT(p_{i-1},p_{i},(q_{i,1},q_{i,2},\dots ,q_{i,K}))}$

(La marcha de Jarvis finaliza cuando el siguiente punto seleccionado en la envolvente convexa, ${\displaystyle p_{i+1}}$, es el punto inicial, ${\displaystyle p_{1}}$).

si ${\displaystyle p_{i+1}==p_{1}}$

(Devuelve la envolvente convexa de ${\displaystyle P}$, que contiene ${\displaystyle i=h}$ puntos).

(Nota: por supuesto, no es necesario devolver ${\displaystyle p_{i+1}}$, que es igual a ${\displaystyle p_{1}}$).

devuelve ${\displaystyle C:=(p_{1},p_{2},\dots ,p_{i})}$

si no

${\displaystyle ADD(C,p_{i+1})}$

(Si después de ${\displaystyle m}$ iteraciones no se ha encontrado un punto ${\displaystyle p_{i+1}}$ tal que ${\displaystyle p_{i+1}==p_{1}}$, entonces ${\displaystyle m<h}$).

(Se necesita comenzar de nuevo con un valor mayor para ${\displaystyle m}$).