DIVIDE Y VENCERÁS
GENÉRICO


NOTAS PREVIAS


Este método es una variación del algoritmo Divide y Vencerás con Preordenación. Para su ejecución se necesitará conocer el concepto de Recta Soporte y el algoritmo Scan de Graham


DESCRIPCIÓN DEL ALGORITMO


Sea S el conjunto de puntos, ordenados de forma arbitraria


Cierre de S
  1. Si hay un punto en S, entonces ese punto es el cierre convexo
    Si hay dos puntos en S, entonces el cierre convexo es el segmento que los une
    Si hay tres puntos en S, entonces el cierre es el triángulo formado por ellos

    Si hay más de tres puntos

  2. Dividir S en dos subconjuntos S1 y S2 según ese orden arbitrario
  3. Calcular el cierre de S1 obteniendo P1
  4. Calcular el cierre de S2 obteniendo P2
  5. Mezclar los cierres P1 y P2 para obtener P, el cierre de S.


    Esta Mezcla se realiza de la siguiente forma:
  1. Obtener un punto p interno a P1

  2. Si p es interno a P2:

    1. Mezclar los vértices de P1 y P2 obteniendo P12
    2. Aplicar Scan de Graham a P12 para obtener el cierre P

  3. Si p es externo a P2:

    1. Hallar las rectas soporte de p respecto a P2
    2. Los vértices entre las rectas se descartan
    3. El resto de vértices se mezclan con P2 obteniendo P12
    4. Aplicar Scan de Graham a P12 para obtener el cierre P


COMPLEJIDAD DEL ALGORITMO

O(N.LogN)