Algoritmo de Chan

Algoritmo para encontrar la envoltura convexa de un conjunto de puntos en el plano

Una demostración en 2D del algoritmo de Chan. Sin embargo, tenga en cuenta que el algoritmo divide los puntos de manera arbitraria, no por la coordenada x.

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] ${\displaystyle P}$ ${\displaystyle n}$ ${\displaystyle O(n\log h)}$ ${\displaystyle h}$ ${\displaystyle O(n\log n)}$ ${\displaystyle O(nh)}$ ${\displaystyle O(n\log h)}$

Algoritmo

Descripción general

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 ). ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle P}$ ${\displaystyle m=h}$ ${\displaystyle h}$ ${\displaystyle m}$ ${\displaystyle m\geq h}$ ${\displaystyle m}$

El algoritmo comienza dividiendo arbitrariamente el conjunto de puntos en subconjuntos con como máximo puntos cada uno; observe que . ${\displaystyle P}$ ${\displaystyle K=\lceil n/m\rceil }$ ${\displaystyle (Q_{k})_{k=1,2,...K}}$ ${\displaystyle 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}}$ ${\displaystyle C_{k}}$ ${\displaystyle O(p\log p)}$ ${\displaystyle p}$ ${\displaystyle 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}}$ ${\displaystyle p_{i}}$ ${\displaystyle p_{i}}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle p_{i+1}=f(p_{i},P)}$ ${\displaystyle P}$ ${\displaystyle p_{i}p_{i+1}}$ ${\displaystyle p_{i+1}=f(p_{i},P)}$ ${\displaystyle p_{i+1}}$ ${\displaystyle p_{i}}$ ${\displaystyle P}$ ${\displaystyle Q_{k}}$ ${\displaystyle C_{k}}$ ${\displaystyle m}$ ${\displaystyle f(p_{i},Q_{k})}$ ${\displaystyle O(\log m)}$ ${\displaystyle f(p_{i},Q_{k})}$ ${\displaystyle K}$ ${\displaystyle O(K\log m)}$ ${\displaystyle f(p_{i},P)}$ ${\displaystyle (f(p_{i},Q_{k}))_{1\leq k\leq K}}$ ${\displaystyle P}$ ${\displaystyle O(K)}$ ${\displaystyle O(h)}$ ${\displaystyle h}$ ${\displaystyle h}$ ${\displaystyle P}$ ${\displaystyle O(Kh\log m)}$ ${\displaystyle O(n\log h)}$ ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle m}$

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

Elección del parámetrometro

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. ${\displaystyle m}$ ${\displaystyle m<h}$ ${\displaystyle 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 . ${\displaystyle m}$ ${\displaystyle O(n\log m)}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle h}$ ${\displaystyle O(n\log m)>O(n\log h)}$

Estrategia de cuadratura

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 ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle 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 ${\displaystyle 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).}$

En tres dimensiones

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)}$

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

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

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

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

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

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

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

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

(Nota: no es un punto de .) ${\displaystyle p_{0}}$ ${\displaystyle 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 .) ${\displaystyle h}$ ${\displaystyle P}$

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

( es necesario para que este algoritmo de Chan encuentre la envoltura convexa de .) ${\displaystyle h\leq m}$ ${\displaystyle 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}$ ${\displaystyle m}$

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

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

es decir, incluso si , no realiza iteraciones del bucle más externo). ${\displaystyle m\neq h}$ ${\displaystyle 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 ). ${\displaystyle C}$ ${\displaystyle 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. ${\displaystyle m}$

Existen otros esquemas: por ejemplo, el "esquema de duplicación", donde , para . ${\displaystyle m=2^{t}}$ ${\displaystyle t=1,\dots ,\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). ${\displaystyle P}$

${\displaystyle C:=()}$

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

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

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

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

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

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 k\leq K}$

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

( es la envoltura convexa del subconjunto de puntos .) ${\displaystyle 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}$

Implementación

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.

Extensiones

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}$

Véase también

• Algoritmos de envoltura convexa

Referencias

1. Chan, Timothy M. (1996). "Algoritmos de envoltura convexa sensibles a la salida óptima en dos y tres dimensiones". Geometría discreta y computacional . 16 (4): 361–368. doi : 10.1007/BF02712873 .
2. Nielsen, Frank (2000). "Agrupamiento y consulta: un paradigma para obtener algoritmos sensibles a la salida". Geometría discreta y computacional . Apuntes de clase en informática. Vol. 1763. págs. 250–257. doi : 10.1007/978-3-540-46515-7_21 . ISBN . 978-3-540-67181-7.
3. Frank Nielsen. "Geometría computacional adaptativa". Tesis doctoral, INRIA , 1996.
4. Chazelle, Bernard ; Matoušek, Jiří (1995). "Desaleatorización de un algoritmo de envoltura convexa sensible a la salida en tres dimensiones". Geometría computacional . 5 : 27–32. doi : 10.1016/0925-7721(94)00018-Q .
5. Hershberger, John (1989). "Encontrar la envolvente superior de n segmentos de línea en tiempo O(n log n)". Information Processing Letters . 33 (4): 169–174. doi :10.1016/0020-0190(89)90136-1.