El PROBLEMA DE ENCONTRAR PUNTOS MÁXIMOS EN UN ESPACIO BIDIMENSIONAL

En el espacio bidimensional se dice que un punto (x1,y1) domina a (x2, y2) si x1 > x2 y y1 > y2. Un punto se denomina máximo si ningún otro punto lo domina. Así, dado un conjunto de n puntos, el problema de encontrar los máximos consiste en encontrar todos los puntos máximos de entre estos n puntos. Por ejemplo, los puntos encerrados en un círculo de la siguiente gráfica:

Un método directo para resolver el problema de encontrar los máximos consiste en comparar cada par de puntos. Este método directo requiere O(n^2) comparaciones de puntos. Como se mostrará a continuación, si se aplica la estrategia divide-y-vencerás, el problema puede resolverse en O(n log n) pasos, lo cual constituye, de hecho, una mejora bastante aceptable.
Si se aplica la estrategia divide-y-vencerás, primero se encuentra la recta mediana L perpendicular al eje x, que divide en dos subconjuntos todo el conjunto de puntos, como se muestra a continuación:

Los conjuntos de puntos a la izquierda de L y a la derecha de L se denotan por SL y SR, respectivamente.

El siguiente paso es encontrar en forma recurrente los puntos máximos de SL y SR. Como se muestra en la figura, P1,P2 y P3 son puntos máximos de SL y P8, P9 y P10 son puntos máximos de SR.

El proceso de fusión es muy sencillo. Debido a que el valor x de un punto en SR siempre es mayor que el valor x de todo punto en SL, un punto en SL es un máximo si y sólo si su valor y no es menor que el valor y de un máximo de SR. Por ejemplo, para el caso que se muestra en la figura, P3 debe eliminarse porque es dominado por P8 en SR. El conjunto de puntos máximos de S es P1, P2, P8, P9 y P10.

Con base en el análisis anterior, podemos resumir como sigue el algoritmo divide-y-vencerás para resolver el problema:

Entrada: Un conjunto de n puntos planos.
Salida: Los puntos máximos de S.

Paso 1. Si S sólo contiene un punto, proporcionarlo como el máximo. En caso contrario, encontrar una recta L perpendicular al eje x que separe el conjunto de puntos en dos subconjuntos SL y SR, cada uno con n/2 puntos.

Paso 2. Los puntos máximos de SL y SR se encuentran de manera recursiva.

Paso 3. Los puntos máximos de SL y SR se proyectan sobre L y se ordenan según sus valores y. Sobre las proyecciones se realiza una exploración lineal y cada uno de los puntos máximos de SL se elimina si su valor y es menor que el valor y de algún punto máximo de SR.

La complejidad temporal de este algoritmo depende de las complejidades temporales de los pasos siguientes:

1. En el paso 1 hay una operación que encuentra la mediana de n números. Después se demostrará que esto puede hacerse en O(n) pasos.
2. En el paso 2 hay dos subproblemas, cada uno con n/2 puntos.
3. En el paso 3, la proyección y la exploración lineal pueden hacerse en O(n log n) pasos después de ordenar los n puntos según sus valores y.

Estos órdenes (O(n) y O (n log n)) son los que debemos agregar a la ecuación de recurrencia para determinar la eficiencia total del algoritmo. Ahora, hay que resolver la ecuación de recurrencia T(n), es decir, la complejidad temporal del algoritmo divide-y-vencerás para encontrar puntos máximos de n puntos en un plano. Entonces:

T(1) = 1

T(n) = 2T(n/2) + O (n) + O(n log n)

Sea n = 2^k . Entonces: T(n) = O(n log n) + O(n log^2 n) = O(n log^2 n).

Así, se ha obtenido un algoritmo O(n log^2 n).

Podemos observar que la estrategia divide-y-vencerás es dominada por el ordenamiento en los pasos de fusión (o mezcla). De alguna manera, ahora no se está realizando un trabajo muy eficiente porque el ordenamiento debe hacerse de una vez por todas. Es decir, debe hacerse un preordenamiento. Si esto se lleva a cabo, entonces la complejidad de la mezcla es O(n) y el número total de pasos necesarios es O(n log n) + T(n) donde

T(1) = 1

T(n) = 2T(n/2) + O (n) + O (n)

y fácilmente se encuentra que T(n) es O(n log n). Así, la complejidad temporal total de usar la estrategia divide-y-vencerás para encontrar puntos máximos con preordenamiento es O(n log n). En otras palabras, se tiene un algoritmo aún más eficiente.

Ejercicios:

Implemente el algoritmo para encontrar rangos con base en el método divide-y-vencerás. Compárelo con el método directo.

Implemente el algoritmo de la transformada rápida de Fourier con base en el método divide-y-vencerás. Compárelo con el método directo.