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 el casco convexo de un conjunto. de puntos, en espacio bidimensional o tridimensional. El algoritmo toma tiempo, donde es el número de vértices de la salida (el casco convexo). En el caso plano, el algoritmo combina unalgoritmo ( escaneo de Graham , por ejemplo) con Jarvis march (), con el fin de obtener un óptimo hora. El algoritmo de Chan es notable porque es mucho más simple que el algoritmo de Kirkpatrick-Seidel y, naturalmente, se extiende al espacio tridimensional. Este paradigma [2] ha sido desarrollado independientemente por Frank Nielsen en su Ph.D. tesis. [3]
Algoritmo
Descripción general
Un solo paso del algoritmo requiere un parámetro que está entre 0 y (número de puntos de nuestro conjunto ). Idealmente, pero , el número de vértices en el casco convexo de salida, no se conoce al principio. Múltiples pases con valores crecientes de se hacen que luego terminan cuando (ver más abajo sobre la elección del parámetro ).
El algoritmo comienza dividiendo arbitrariamente el conjunto de puntos. dentro subconjuntos con como máximo puntos cada uno; Darse cuenta de.
Para cada subconjunto , calcula el casco convexo, , usando un algoritmo (por ejemplo, escaneo de Graham ), dondees el número de puntos del subconjunto. Como los hay subconjuntos de puntos cada uno, esta fase lleva hora.
Durante la segunda fase, se ejecuta la marcha de Jarvis , haciendo uso de los cascos convexos (mini) calculados previamente,. En cada paso del algoritmo de marcha de Jarvis, tenemos un punto en el casco convexo (al principio, puede ser el punto en con la coordenada y más baja, que se garantiza que estará en el casco convexo de ), y necesito 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 en función de y . El casco convexo del conjunto, , es conocido y contiene como máximo puntos (enumerados en sentido horario o antihorario), lo que permite calcular en tiempo por búsqueda binaria [ ¿cómo? ] . Por tanto, el cálculo de por todos los los subconjuntos se pueden hacer en hora. Entonces, podemos determinar usando la misma técnica que se usa normalmente en la marcha de Jarvis, pero solo considerando los puntos (es decir, los puntos en los cascos mini convexos) en lugar de todo el conjunto . Para esos puntos, una iteración de la marcha de Jarvis esque es insignificante en comparación con el cálculo de todos los subconjuntos. La marcha de Jarvis se completa cuando se ha repetido el proceso 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 el casco convexo de , debemos haber encontrado el casco convexo), por lo que la segunda fase toma tiempo, equivalente a tiempo si esta cerca de (ver más abajo la descripción de una estrategia a elegir tal que este sea el caso).
Al ejecutar las dos fases descritas anteriormente, el casco convexo de puntos se calcula en hora.
Elegir el parámetro
Si se elige un valor arbitrario para , puede suceder que . En ese caso, despuéspasos en la segunda fase, interrumpimos la marcha del Jarvis ya que llevarlo hasta el final llevaría demasiado tiempo. En ese momento, un se habrá gastado tiempo y no se habrá calculado el casco convexo.
La idea es realizar varias pasadas del algoritmo con valores crecientes de ; cada pase termina (con éxito o sin éxito) enhora. Siaumenta demasiado lentamente entre pasadas, el número de iteraciones puede ser grande; por otro lado, si sube demasiado rápido, el primer para el cual el algoritmo termina con éxito puede ser mucho mayor que y producir una complejidad .
Estrategia de cuadratura
Una posible estrategia es elevar al cuadrado el valor de en cada iteración, hasta un valor máximo de (correspondiente a una partición en conjuntos singleton). [4] A partir de un valor de 2, en la iteración, esta elegido. En ese caso, se realizan iteraciones, dado que el algoritmo termina una vez que tenemos
con el logaritmo tomado en base , y el tiempo total de ejecución del algoritmo es
En tres dimensiones
Para generalizar esta construcción para el caso tridimensional, un Se debe usar un algoritmo para calcular el casco convexo tridimensional de Preparata y Hong en lugar del escaneo de Graham, y se debe usar una versión tridimensional de la marcha de Jarvis. La complejidad del tiempo permanece. [1]
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 el escaneo de Graham y los algoritmos de marcha de Jarvis para calcular el casco convexo,, de un conjunto de puntos, .
- Entrada: Establecer con puntos .
- Salida: Establecer con puntos, el casco convexo de .
- (Elija un punto de que está garantizado para estar en : por ejemplo, el punto con la coordenada y más baja.)
- (Esta operación toma tiempo: por ejemplo, podemos simplemente iterar a través .)
- ( se utiliza en la parte de marcha de Jarvis del algoritmo de este Chan,
- de modo que para calcular el segundo punto, , en el casco convexo de .)
- (Nota: no es un punto de.)
- (Para obtener más información, consulte los comentarios cerca de la parte correspondiente del algoritmo de Chan).
- (Nota: , el número de puntos en el casco convexo final de , no se conoce.)
- (Estas son las iteraciones necesarias para descubrir el valor de , que es una estimación de .)
- ( es necesario para que el algoritmo de este Chan encuentre el casco convexo de .)
- (Más específicamente, queremos , para no realizar demasiadas iteraciones innecesarias
- y para que la complejidad temporal del algoritmo de este Chan sea .)
- (Como se explicó anteriormente en este artículo, usamos una estrategia en la que como máximo se requieren iteraciones para encontrar .)
- (Nota: el final puede no ser igual a , pero nunca es más pequeño que y mayor que .)
- (Sin embargo, el algoritmo de este Chan se detiene una vez se realizan iteraciones del bucle más externo,
- es decir, incluso si , no funciona iteraciones del bucle más externo.)
- (Para obtener más información, consulte la parte de marcha de Jarvis de este algoritmo a continuación, donde se devuelve si .)
- porhacer
- (Establecer parámetro para la iteración actual. Usamos un "esquema de cuadratura" como se describe anteriormente en este artículo.
- Hay otros esquemas: por ejemplo, el "esquema de duplicación", donde , por .
- Sin embargo, si usamos el "esquema de duplicación", la complejidad de tiempo resultante del algoritmo de este Chan es .)
- (Inicialice una lista (o matriz) vacía para almacenar los puntos del casco convexo de , como se encuentran.)
- (Conjunto de puntos dividido arbitrariamente dentro subconjuntos de aproximadamente elementos cada uno.)
- (Calcule el casco convexo de todos subconjuntos de puntos, .)
- (Se necesita hora.)
- Si , entonces la complejidad del tiempo es .)
- porhacer
- (Calcule el casco convexo del subconjunto , , usando el escaneo de Graham, que toma hora.)
- ( es el casco convexo del subconjunto de puntos .)
- (En este punto, los cascos convexos de respectivamente los subconjuntos de puntos han sido calculados.)
- (Ahora, use una versión modificada del algoritmo de marcha de Jarvis para calcular el casco convexo de.)
- (Jarvis march actúa en tiempo, donde es el número de puntos de entrada y es el número de puntos en el casco convexo.)
- (Dado que la marcha de Jarvis es un algoritmo sensible a la salida , su tiempo de ejecución depende del tamaño del casco convexo,.)
- (En la práctica, significa que Jarvis march realiza iteraciones de su bucle más externo.
- En cada una de estas iteraciones, realiza como máximo iteraciones de su bucle más interno).
- (Queremos , por lo que no queremos realizar más de iteraciones en el siguiente bucle externo.)
- (Si nuestra actual es más pequeña que , es decir , el casco convexo de no pudo ser encontrado.)
- (En esta versión modificada de la marcha de Jarvis, realizamos una operación dentro del bucle más interno que toma hora.
- Por lo tanto, la complejidad de tiempo total de esta versión modificada es
- Si , entonces la complejidad del tiempo es .)
- porhacer
- (Nota: aquí, un punto en el casco convexo de ya se sabe, es decir .)
- (En este bucle for interno , posibles próximos puntos en el casco convexo de , , se calculan.)
- (Cada uno de estos los siguientes puntos posibles son de una :
- es decir, es un posible siguiente punto en el casco convexo de que forma parte del casco convexo de .)
- (Nota: depender de : es decir, para cada iteración , tenemos posibles próximos puntos en el casco convexo de .)
- (Nota: en cada iteración , solo uno de los puntos entre se agrega al casco convexo de .)
- porhacer
- ( encuentra el punto tal que el ángulo se maximiza [ ¿por qué? ] ,
- dónde es el ángulo entre los vectores y . Semejante se almacena en .)
- (No es necesario calcular los ángulos directamente: la prueba de orientación se puede utilizar [ ¿cómo? ] .)
- ( se puede realizar en tiempo [ ¿cómo? ] .)
- (Nota: en la iteración , y es conocido y es un punto en el casco convexo de :
- en este caso, es el punto de con la coordenada y más baja.)
- (Elige el punto que maximiza el ángulo [ ¿por qué? ] para ser el siguiente punto en el casco convexo de.)
- (La marcha de Jarvis termina cuando el siguiente punto seleccionado en el casco convexo, , es el punto inicial, .)
- Si
- (Devuelve el casco convexo de que contiene puntos.)
- (Nota: por supuesto, no es necesario devolver que es igual a .)
- regreso
- demás
- (Si despues iteraciones un punto no se ha encontrado para que , luego .)
- (Necesitamos empezar de nuevo con un valor más alto para .)
Implementación
El artículo de Chan contiene varias sugerencias que pueden mejorar el rendimiento práctico del algoritmo, por ejemplo:
- Al calcular los cascos convexos de los subconjuntos, elimine los puntos que no están en el casco convexo de la consideración en ejecuciones posteriores.
- Los cascos convexos de conjuntos de puntos más grandes se pueden obtener fusionando cascos convexos previamente calculados, en lugar de volver a calcular desde cero.
- Con la idea anterior, el costo dominante del algoritmo radica en el preprocesamiento, es decir, el cálculo de los cascos convexos de los grupos. Para reducir este costo, podemos considerar reutilizar los cascos calculados a partir de la iteración anterior y fusionarlos a medida que aumenta el tamaño del grupo.
Extensiones
El artículo de Chan contiene algunos otros problemas cuyos algoritmos conocidos pueden hacerse sensibles a la 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.
- Hershberger [5] dio un algoritmo que se puede acelerar hasta , donde h es el número de bordes del sobre
- Construcción de algoritmos sensibles a la salida para cascos convexos de mayor dimensión. Con el uso de puntos de agrupación y el uso de estructuras de datos eficientes, la complejidad se puede lograr siempre que h sea de orden polinomial en .
Ver también
Referencias
- ^ a b Timothy M. Chan. " Algoritmos óptimos de cascos convexos sensibles a la salida en dos y tres dimensiones ". Geometría discreta y computacional , vol. 16, págs. 361–368. 1996.
- ^ Frank Nielsen. " Agrupación y consulta: un paradigma para obtener algoritmos sensibles a la salida ". Geometría discreta y computacional , LNCS 1763, págs. 250-257, 2000.
- ^ Frank Nielsen. " Geometría computacional adaptativa ". Doctor. tesis, INRIA , 1996.
- ^ B. Chazelle Jiří Matoušek. " Desaleatorizar un algoritmo de casco convexo sensible a la salida en tres dimensiones ". Geometría computacional , vol. 5, págs. 27–32. 1995.
- ^ J. Hershberger. " Encontrar la envolvente superior de n segmentos de línea en el tiempo O (n log n) ". Cartas de procesamiento de información , vol. 33, págs. 169-174. 1989.