Algoritmo de Chan

En geometría computacional , el algoritmo de Chan , ^[1] llamado así por Timothy M. Chan , es un algoritmo óptimo sensible a la salida para calcular la envoltura convexa de un conjunto de puntos, en un espacio bidimensional o tridimensional. El algoritmo lleva tiempo, donde es el número de vértices de la salida (la envoltura convexa). En el caso planar, el algoritmo combina un algoritmo ( Graham scan , por ejemplo) con Jarvis march ( ), para obtener un tiempo óptimo. El algoritmo de Chan es notable porque es mucho más simple que el algoritmo de Kirkpatrick-Seidel , y se extiende naturalmente al espacio tridimensional. Este paradigma ^[2] ha sido desarrollado independientemente por Frank Nielsen en su tesis doctoral. ^[3]${\estilo de visualización P}$${\estilo de visualización n}$${\displaystyle O(n\log h)}$${\estilo de visualización h}$${\displaystyle O(n\log n)}$${\displaystyle O(nh)}$${\displaystyle O(n\log h)}$

Una sola pasada del algoritmo requiere un parámetro que esté entre 0 y (número de puntos de nuestro conjunto ). Lo ideal sería que , pero , el número de vértices en la envoltura convexa de salida, no se conozca al principio. Se realizan varias pasadas con valores crecientes de que luego finalizan cuando (ver más abajo sobre la elección del parámetro ). ${\estilo de visualización m}$${\estilo de visualización n}$${\estilo de visualización P}$${\displaystyle m=h}$${\estilo de visualización h}$${\estilo de visualización m}$${\displaystyle m\geq h}$${\estilo de visualización m}$

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

Para cada subconjunto , calcula la envoltura convexa, , utilizando un algoritmo (por ejemplo, el escaneo de Graham ), donde es el número de puntos en el subconjunto. Como hay subconjuntos de puntos cada uno, esta fase lleva tiempo. ${\displaystyle Q_{k}}$$Estilo de visualización C_{k}}$${\displaystyle O(p\log p)}$${\estilo de visualización p}$${\estilo de visualización K}$${\displaystyle O(m)}$${\displaystyle K\cdot O(m\log m)=O(n\log m)}$

Durante la segunda fase, se ejecuta la marcha de Jarvis , haciendo uso de las (mini) envolturas convexas precalculadas, . En cada paso de este algoritmo de la marcha de Jarvis, tenemos un punto en la envoltura convexa (al principio, puede ser el punto en con la coordenada y más baja, que se garantiza que está en la envoltura convexa de ), y necesitamos encontrar un punto tal que todos los demás puntos de estén a la derecha de la línea ^{[ aclaración necesaria ]} , donde la notación simplemente significa que el siguiente punto, es decir , se determina como una función de y . La envoltura convexa del conjunto , , es conocida y contiene como máximo puntos (enumerados en sentido horario o antihorario), lo que permite calcular en el tiempo mediante búsqueda binaria ^{[ ¿ cómo? ]} . Por lo tanto, el cálculo de para todos los subconjuntos se puede hacer en el tiempo. Entonces, podemos determinar usando la misma técnica que normalmente se usa en la marcha de Jarvis, pero solo considerando los puntos (es decir, los puntos en las mini envolturas convexas) en lugar de todo el conjunto . Para esos puntos, una iteración de la marcha de Jarvis es que es despreciable en comparación con el cálculo para todos los subconjuntos. La marcha de Jarvis se completa cuando el proceso se ha repetido veces (porque, en la forma en que funciona la marcha de Jarvis, después de como máximo iteraciones de su bucle más externo, donde es el número de puntos en la envoltura convexa de , debemos haber encontrado la envoltura convexa), por lo tanto, la segunda fase toma tiempo, equivalente al tiempo si es cercano a (ver más abajo la descripción de una estrategia a elegir de manera que este sea el caso). ${\displaystyle (C_{k})_{k=1,2,...K}}$$estilo de visualización p_{i}}$$estilo de visualización p_{i}}$${\estilo de visualización P}$${\estilo de visualización P}$${\displaystyle p_{i+1}=f(p_{i},P)}$${\estilo de visualización P}$$estilo de visualización p_{i}p_{i+1}}$${\displaystyle p_{i+1}=f(p_{i},P)}$$estilo de visualización p_{i+1}}$$estilo de visualización p_{i}}$${\estilo de visualización P}$${\displaystyle Q_{k}}$$Estilo de visualización C_{k}}$${\estilo de visualización m}$${\displaystyle f(p_{i},Q_{k})}$${\displaystyle O(\log m)}$${\displaystyle f(p_{i},Q_{k})}$${\estilo de visualización K}$${\displaystyle O(K\log m)}$${\displaystyle f(p_{i},P)}$${\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}$${\estilo de visualización P}$${\displaystyle O(K)}$${\displaystyle O(h)}$${\estilo de visualización h}$${\estilo de visualización h}$${\estilo de visualización P}$${\displaystyle O(Kh\log m)}$${\displaystyle O(n\log h)}$${\estilo de visualización m}$${\estilo de visualización h}$${\estilo de visualización m}$

Ejecutando las dos fases descritas anteriormente, se calcula la envoltura convexa de puntos en el tiempo. ${\estilo de visualización n}$${\displaystyle O(n\log h)}$

Si se elige un valor arbitrario para , puede ocurrir que . En ese caso, después de los pasos de la segunda fase, interrumpimos la marcha de Jarvis porque llevarla hasta el final llevaría demasiado tiempo. En ese momento, se habrá gastado un tiempo y no se habrá calculado la envoltura convexa. ${\estilo de visualización m}$${\displaystyle m<h}$${\estilo de visualización m}$${\displaystyle O(n\log m)}$

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

Una posible estrategia es elevar al cuadrado el valor de en cada iteración, hasta un valor máximo de (que corresponde a una partición en conjuntos singleton). ^[4] Partiendo de un valor de 2, en la iteración se elige . En ese caso, se realizan iteraciones, dado que el algoritmo termina una vez que tenemos ${\estilo de visualización m}$${\estilo de visualización n}$${\estilo de visualización t}$${\displaystyle m=\min \left(n,2^{2^{t}}\right)}$${\displaystyle O(\log \log h)}$

${\displaystyle m=2^{2^{t}}\geq h\iff \log \left(2^{2^{t}}\right)\geq \log h\iff 2^{t}\geq \log h\iff \log {2^{t}}\geq \log {\log h}\iff t\geq \log {\log h},}$

con el logaritmo tomado en base , y el tiempo total de ejecución del algoritmo es ${\estilo de visualización 2}$

${\displaystyle \sum _{t=0}^{\lceil \log \log h\rceil }O\left(n\log \left(2^{2^{t}}\right)\right)=O(n)\sum _{t=0}^{\lceil \log \log h\rceil }2^{t}=O\left(n\cdot 2^{1+\lceil \log \log h\rceil }\right)=O(n\log h).}$

Para generalizar esta construcción para el caso tridimensional, se debe utilizar un algoritmo para calcular la envoltura convexa tridimensional de Preparata y Hong en lugar del escaneo de Graham, y se debe utilizar una versión tridimensional de la marcha de Jarvis. La complejidad temporal sigue siendo . ^[1]${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

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 ya esté familiarizado con los algoritmos de Graham Scan y Jarvis March para calcular la envoltura convexa, , de un conjunto de puntos, . ${\estilo de visualización C}$${\estilo de visualización P}$

Entrada: Conjunto con puntos.${\estilo de visualización P}$${\estilo de visualización n}$

Salida: Conjunto con puntos, la envoltura convexa de .${\estilo de visualización C}$${\estilo de visualización h}$${\estilo de visualización P}$

(Elija un punto que esté garantizado que esté en : por ejemplo, el punto con la coordenada y más baja).${\estilo de visualización P}$${\estilo de visualización C}$

(Esta operación lleva tiempo: por ejemplo, podemos simplemente iterar a través de ).${\displaystyle {\mathcal {O}}(n)}$${\estilo de visualización P}$

${\displaystyle p_{1}:=SELECCIONAR\_INICIO(P)}$

( se utiliza en la parte de la marcha de Jarvis de este algoritmo de Chan,$estilo de visualización p_{0}}$

de modo que para calcular el segundo punto, , en la envoltura convexa de .)${\estilo de visualización p_{2}}$${\estilo de visualización P}$

(Nota: no es un punto de .)$estilo de visualización p_{0}}$${\estilo de visualización P}$

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

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

(Nota: , no se conoce el número de puntos en la envoltura convexa final de .)${\estilo de visualización h}$${\estilo de visualización P}$

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

( es necesario para que este algoritmo de Chan encuentre la envoltura convexa de .)${\displaystyle h\leq m}$${\estilo de visualización P}$

(Más específicamente, queremos , para no realizar demasiadas iteraciones innecesarias${\displaystyle h\leq m\leq h^{2}}$

y entonces la complejidad temporal de este algoritmo de Chan es .)${\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 iteraciones para encontrar ).${\displaystyle \log \log n}$${\estilo de visualización m}$

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

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

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

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

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

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

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

Sin embargo, 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}}}$

(Inicialice una lista (o matriz) vacía para almacenar los puntos de la envoltura convexa de , a medida que se encuentran).${\estilo de visualización P}$

${\estilo de visualización C:=()}$

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

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

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

(Calcular la envoltura convexa de todos los subconjuntos de puntos, .)${\estilo de visualización K}$${\displaystyle Q_{1},Q_{2},\puntos ,Q_{K}}$

(Toma tiempo.)${\displaystyle {\mathcal {O}}(Km\log m)={\mathcal {O}}(n\log m)}$

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

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

(Calcule la envoltura convexa del subconjunto , , utilizando el escaneo de Graham, lo que lleva tiempo).${\estilo de visualización k}$${\displaystyle Q_{k}}$${\displaystyle {\mathcal {O}}(m\log m)}$

( es la envoltura convexa del subconjunto de puntos .)$Estilo de visualización C_{k}}$${\displaystyle Q_{k}}$

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

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

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

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

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

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

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

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

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

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

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 , entonces la complejidad temporal es .)${\displaystyle m\leq h^{2}}$${\displaystyle {\mathcal {O}}(n\log h^{2})={\mathcal {O}}(n\log h)}$

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

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

(En este bucle for interno, se calculan los posibles próximos puntos que estarán en la envoltura convexa de , , ).${\displaystyle K}$${\displaystyle P}$${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$

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

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

(Nota: depende de : es decir, para cada iteración , hay posibles próximos puntos que pueden estar en la envoltura convexa de .)${\displaystyle q_{i,1},q_{i,2},\dots ,q_{i,K}}$${\displaystyle i}$${\displaystyle i}$${\displaystyle K}$${\displaystyle P}$

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

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

( encuentra el punto tal que el ángulo se maximiza ^{[ ¿por qué? ]} ,${\displaystyle JARVIS\_BINARY\_SEARCH}$${\displaystyle d\in C_{k}}$${\displaystyle \measuredangle p_{i-1}p_{i}d}$

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

(No es necesario calcular los ángulos directamente: se puede utilizar la prueba de orientación ^{[ ¿cómo? ]} .)

( se puede realizar a tiempo ^{[ ¿cómo? ]} )${\displaystyle JARVIS\_BINARY\_SEARCH}$${\displaystyle {\mathcal {O}}(\log m)}$

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

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

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

(Elija el punto que maximiza el ángulo ^{[ ¿por qué? ]} para que sea el siguiente punto en la envoltura convexa de .)${\displaystyle z\in \{q_{i,1},q_{i,2},\dots ,q_{i,K}\}}$${\displaystyle \measuredangle p_{i-1}p_{i}z}$ ${\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 termina cuando el siguiente punto seleccionado en la envoltura convexa, , es el punto inicial, .)${\displaystyle p_{i+1}}$${\displaystyle p_{1}}$

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

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

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

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

demás

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

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

(Necesitamos empezar de nuevo con un valor más alto para .)${\displaystyle m}$

El artículo de Chan contiene varias sugerencias que pueden mejorar el rendimiento práctico del algoritmo, por ejemplo:

• Al calcular las envolturas convexas de los subconjuntos, elimine los puntos que no estén en la envoltura convexa para que no se consideren en ejecuciones posteriores.
• Las envolturas convexas de conjuntos de puntos más grandes se pueden obtener fusionando envolturas convexas calculadas previamente, en lugar de volver a calcular desde cero.
• Con la idea anterior, el costo dominante del algoritmo reside en el preprocesamiento, es decir, el cálculo de las envolturas convexas de los grupos. Para reducir este costo, podemos considerar reutilizar las envolturas calculadas a partir de la iteración anterior y fusionarlas a medida que aumenta el tamaño del grupo.

El artículo de Chan contiene algunos otros problemas cuyos algoritmos conocidos pueden lograrse con una salida óptima utilizando su técnica, por ejemplo:

• Calcular la envolvente inferior de un conjunto de segmentos de línea, que se define como el límite inferior del trapezoide ilimitado formado por las intersecciones.${\displaystyle L(S)}$${\displaystyle S}$${\displaystyle n}$
• Hershberger ^[5] presentó un algoritmo que puede acelerarse hasta , donde h es el número de aristas en la envolvente.${\displaystyle O(n\log n)}$${\displaystyle O(n\log h)}$

• Construcción de algoritmos sensibles a la salida para envolventes convexas de dimensiones superiores. Con el uso de puntos de agrupación y estructuras de datos eficientes, se puede lograr la complejidad siempre que h sea de orden polinomial en .${\displaystyle O(n\log h)}$${\displaystyle n}$

• Algoritmos de envoltura convexa