Algoritmo de caparazón rápido

El algoritmo de casco rápido  es un algoritmo para construir un casco convexo en un avión. Utiliza la idea de Quicksort de Hoare

Descripción

El conjunto de puntos se divide en dos subconjuntos, cada uno de los cuales contendrá una de las líneas discontinuas, cuya conexión da el polígono de casco convexo.

  1. Tomemos dos puntos extremos del conjunto S: el L izquierdo y el P derecho. Tracemos una línea recta a través de ellos. Denótese por S1 el subconjunto de puntos situados por encima o sobre la recta que pasa por los puntos A y P, y por S2 el subconjunto de puntos situados por debajo o sobre la misma recta.
  2. Considere el subconjunto superior S1. Elegimos el punto Pi, que tiene la mayor distancia a la recta LP (el triángulo LPiP tiene el área más grande). Si hay varios de estos puntos, elegimos el que tiene el ángulo PiLP más grande. El punto Pi es el vértice de la envolvente convexa del conjunto. En efecto, si se traza una recta paralela a la recta LP por el punto Pi, entonces no habrá un solo punto del conjunto S por encima de esta recta, es posible que haya otros puntos sobre la recta construida, pero, según a la elección realizada, Pi es el más a la izquierda de ellos. Que. El punto Pi no puede ser representado por una combinación convexa de otros dos puntos del conjunto S. Construyamos líneas LPi y PiP. Los puntos ubicados a la derecha de ambas líneas pueden ser excluidos de mayor consideración, ya que son puntos interiores del triángulo LPiP, es decir, no pertenecen a CH(S), el límite del casco convexo.
  3. Ahora considere el subconjunto de puntos S11 ubicado a la izquierda de la línea ЛPi o sobre ella, y el subconjunto de puntos S12 ubicado a la izquierda de la línea PiП o sobre ella. Para cada uno de los subconjuntos construimos un casco convexo. La envolvente convexa del conjunto S1 se forma pegando las listas ordenadas de vértices CH(S11) y CH(S12).
  4. Resolvemos el problema para S2.

Complejidad del algoritmo

La complejidad del algoritmo consiste en la complejidad de construir dos subconjuntos del conjunto considerado O(N) y la complejidad de resolver subproblemas para cada uno de los subconjuntos: T(N) = T(a) + T(b) + O( NORTE).

En el mejor de los casos, cuando la tarea se divide en dos subtareas igualmente poderosas, la complejidad del algoritmo es la solución de la ecuación recursiva:

(1) T(N) = 2 T(N/2) + O(N) =>

(2) T(N) = O(N log N).

Lo peor:

(3) T(N) = T(1) + T(N 1) + O(N) =>

(4) T(N) = O(N^2).

Lema La solución a la ecuación (1) es la función (2) Sea N = 2k. Entonces T(2k) = 2 T(2k 1) + C 2k ; T(2k 1) = 2 T(2k 2) + C 2k 1 => T(2k) = 4 T(2k 2) + 2 °C 2k 1 + С 2k = 4 T(2k 2) + 2 °C 2k => T(2k) = 2m T(2k m) + m C 2k Para m = k (= logN), el algoritmo termina: T(N) = NT(1) + C logN N = O(N logN)

Véase también

Enlaces