Prog3: Duda teórica - encontrando el par más cercano de puntos

Buenas, tengo la siguiente duda en cómo se arman los conjuntos Qx, Rx, Qy y Ry.

Según entiendo, el libro dice que recorriendo Px y Py armamos esos conjuntos, pero yo entiendo que utiliza únicamente Px. Dice que se arma el conjunto Q según los primeros n/2 elementos de Px (redondeado hacia arriba), luego arma Qx con los elementos de Q ordenados según x, y despues arma Qy a partir de los elementos de Q pero ordenados según y. Tambien arma el conjunto R con los n/2 elementos restantes de Px, y a partir de R arma análogamente los conjuntos Rx y Ry.

Según esto, el conjunto Py no lo utiliza para nada, lo cual no sé si es correcto o no. Dejo la parte teórica abajo en imágenes.

Re: Duda teórica - encontrando el par más cercano de puntos

de Fernando Fernandez - lunes, 3 de octubre de 2022, 17:01

Hola.

Sí, se usa Py para lograr eficiencia. Se trata de construir todas las listas en O(n).

Supongamos que tenemos los puntos de P ya ordenados según las dos coordenadas, por ejemplo:

Px = (1,7), (3,2), (4,8), (5,1), (8,5), (9,3),
Py = (5,1), (3,2), (9,3), (8,5), (1,7), (4,8).

En la llamada inicial el dato es el conjunto P que se preprocesa ordenando según ambos criterios en tiempo

$O(n \log n)$ . En las siguientes llamadas ya podemos suponer que el dato incluye (o consiste en) las dos secuencias ordenadas.

Entonces, en O(n) se recorre Px para determinar Q y R. De hecho, al hacerlo ya se obtienen Qx y Rx:

Qx = (1,7), (3,2), (4,8),
Rx = (5,1), (8,5), (9,3).

Ahora, sabiendo que en Q están los que tienen coordenada x menor o igual a 4, y que en R están los que tienen coordenada mayor o igual a 5 se recorre, también en O(n), Py y se obtienen Qy y Ry:

Qy = (3,2), (1,7), (4,8),
Ry = (5,1), (9,3), (8,5).

Es cierto que Qx=Q y Rx=R. Y por lo tanto se podría haber obtenido Qy reordenado Q según la coordenada y (y Ry reordenando R). Pero hacer eso implicaría tiempos

$O(n \log n)$ en cada paso. La relación de recurrencia pasaría a ser

$T(n) \leq T(n/2) + c n \log n$ .

¿Esto aclara la duda?

Re: Duda teórica - encontrando el par más cercano de puntos

de Marcela Pintos Nogues - lunes, 3 de octubre de 2022, 20:06

Claro ahora entiendo, toma el x máximo en Qx y en base a ese x recorre Py poniendo en Qy los puntos que cumplen con ese x máximo, y luego toma el x mínimo en Rx y en base a ese x pone en Ry los puntos que cumplen con ese y mínimo (lo hace en simultáneo para no recorrer 2 veces).

Muchas gracias!