DIVIDE Y VENCERÁS CON PREORDENACIÓN

NOTAS PREVIAS La idea de la técnica divide y vencerás es dividir un problema en subproblemas del mismo tipo y aproximadamente todos ellos del mismo tamaño, resolver los subproblemas recursivamente y, finalmente, combinar la solución de los subproblemas para dar una solución al problema original. La recursión finaliza cuando el problema es pequeño y la solución es fácil de construir directamente.

DESCRIPCIÓN DEL ALGORITMO Ordenar el conjunto de puntos S de menor a mayor abcisa Cierre de S Si sólo hay un punto, ese punto es el cierre Si no Dividir S por la mitad obteniendo los conjuntos S1 y S2 Calcular el cierre de la mitad izquierda S1 obteniendo P1 Calcular el cierre de la mitad derecha S2 obteniendo P2 Mezclar los cierres P1 y P2 para obtener P, el cierre de S. Esta Mezcla se realiza de la siguiente forma: Se une el vértice más a la derecha de P1 con el más a la izquierda de P2. Este segmento se va desplazando hacia abajo, recorriendo P1 en sentido positivo y P2 en sentido negativo alternativamente, hasta que todos los puntos de S queden por encima. Puente Inferior. Se une el vértice más a la derecha de P1 con el más a la izquierda de P2. Este segmento se va desplazando hacia arriba, recorriendo P1 en sentido negativo y P2 en sentido positivo alternativamente, hasta que todos los puntos de S queden por debajo. Puente Superior

COMPLEJIDAD DEL ALGORITMO Preordenar los puntos: O(N.LogN) Procedimiento Divide y Vencerás: O(N.LogN) O(N.LogN)