Algoritmo de Chen

El algoritmo de Chen es un algoritmo para construir el casco convexo de un conjunto finito de puntos en un plano. Es una combinación de dos algoritmos más lentos ( escaneo de Graham y envoltura de Jarvis ). La desventaja del escaneo de Graham es la necesidad de clasificar todos los puntos por ángulo polar , lo que lleva bastante tiempo . La envoltura de Jarvis requiere iterar sobre todos los puntos para cada uno de los puntos del casco convexo , que en el peor de los casos toma . Nombrado por Timothy M. Chan $O(n\log n)$ $O(nh)$ $O(n\log n)$ $h$ $O(n^{2})$ .

Descripción del algoritmo

La idea del algoritmo de Chen es dividir inicialmente todos los puntos en grupos de piezas en cada uno. En consecuencia, el número de grupos es igual a . Para cada uno de los grupos, se construye un casco convexo escaneando Graham para , es decir, tomará tiempo para todos los grupos . $metro$ $r=\left\lceil n/m\right\rceil$ $O(m\log m)$ $O(rm\log m)=O(n\log m)$

Luego, comenzando desde el punto inferior izquierdo, se construye un casco convexo Jarvis común para los cascos resultantes. En este caso, el siguiente punto adecuado para el casco convexo está detrás , ya que para encontrar un punto con una tangente máxima con respecto al punto considerado en el -gon, basta gastar (los puntos en el -gon fueron ordenados por ángulo polar durante la ejecución del algoritmo de escaneo de Graham). Como resultado, se necesita tiempo para moverse . $O(r\log m)$ $metro$ $O(\log m)$ $metro$ $O(hr\log m)=O\left(\left(hn/m\right)\log m\right)$

Es decir, el algoritmo de Chan funciona para , y si obtiene , entonces para . $O\izquierda(\izquierda(n+hn/m\derecha)\log m\derecha)$ $m=h$ $O(n\log h)$

Casco (P, m) 1) tomar . Divida en subconjuntos disyuntivos de cardinalidad no más de ;

r=\left\lceil n/m\right\rceil

PAGS

r

P_{1},\;P_{2},\;\ldots,\;P_{r}

metro

2) para i = 1 a r hacer : (a) calcule el casco convexo de Graham ( ), almacene los vértices en una matriz ordenada polar;

Pi}

3) tomar el punto más a la izquierda y más bajo de ;

p_{1}

PAGS

4) para k = 1 a m hacer (a) para i = 1 a r hacer encontrar y recordar el punto con el ángulo máximo ;

q_{yo}

Pi}

p_{{k-1}}p_{{k}}q_{i}

(b) tomar como punto desde con el ángulo máximo ;

p_{k+1}

q

{q_{1},\;q_{2},\;\ldots,\;q_{r}}

p_{{k-1}}p_{{k}}q

p_{{k+1}}=p_{1}

{p_{1},\;\ldots,\;p_{k}}

5) devuelve pequeño, inténtalo de nuevo;

metro

Elección del número de puntos m

Está claro que el recorrido de Jarvis, y por lo tanto todo el algoritmo, funcionará correctamente solo si , pero ¿cómo saber de antemano cuántos puntos habrá en el casco convexo? Es necesario ejecutar el algoritmo varias veces, eligiendo y, si , el algoritmo devolverá un error. Si realiza la selección mediante búsqueda binaria en , terminará con el tiempo , que es bastante largo. $m\geqslant h$ $metro$ $m<h$ $norte$ $O((n\log h)\log n)=O(n\log n)$

El proceso se puede acelerar comenzando con un valor pequeño y luego aumentándolo significativamente hasta que funcione . Por ejemplo, tome . En este caso , la iteración -i tomará . El proceso de búsqueda terminará cuando , es decir, ( es el logaritmo binario). $m\geqslant h$ $2^{{2^{t}}}$ $t$ $O(n\registro 2^{{2^{t}}})=O(n2^{t})$ $2^{{2^{t}}}\geqslant h$ $t=\lceil {\mathrm {lg}}\,{\mathrm {lg}}\,h\rceil$ ${\ matemáticas {lg}}$

Al final $\sum _{{t=1}}^{{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}n2^{t}=n\sum_{{t=1} }^{{{\mathrm {lg}}\,{\mathrm {lg}}\,h}}2^{t}\leqslant n2^{{1+{\mathrm {lg}}\,{\mathrm {lg}}\,h}}=2n\,{\mathrm {lg}}\,h=O(n\log h)$

ChanHull (P) para t = 1 an hacer: (a) tomar ;

m=\min(2^{{2^{t}}},\;n)

(b) L = Casco (P, m); (c) si L != " pequeño, inténtalo de nuevo" devuelve L;

metro

Literatura

David M Monte. Geometría Computacional. - Universidad de Maryland, 2002. - 122 p.