ELIMINACIÓN DE LOS PUNTOS INTERIORES

NOTAS PREVIAS Un punto de un conjunto S de puntos es interior al cierre convexo si y sólo si es interior al triángulo cuyos vértices son puntos de S, y no es él mismo un vértice de dicho triángulo.

DESCRIPCIÓN DEL ALGORITMO Para cada tres puntos del conjunto S se descartan los que sean interiores al triángulo formado por ellos. Los puntos que quedan tras este proceso son vértices de la envolvente convexa. Para formar las aristas que constituyen la envolvente convexa basta con ordenarlos angularmente respecto a un punto interior a ellos (calculando la orientación del triángulo formado por ambos vértices y el punto interior alrededor del cual se está realizando la ordenación)

COMPLEJIDAD DEL ALGORITMO Formar los triángulos, comprobar y eliminar los puntos interiores: O(N^4) Ordenar los puntos mediante divide y vencerás: O(N.LogN) O(N^4)