2. ¿Qué se puede concluir de la entrada al algoritmo del par más cercano cuando la salida es cero para las distancias entre un par más cercano?
3. Dé un ejemplo de una entrada para la que el algoritmo del par más cercano coloca algunos puntos que están sobre la línea divisoria l en la mitad izquierda y otros en la derecha.
4. Explique por qué, en algunos casos, al dividir un conjunto de puntos con una línea vertical en dos partes casi iguales, es necesario que la línea contenga algunos de los puntos.
5. Escriba un algoritmo del par más cercano que encuentre un par más cercano al igual que la distancia entre el par de puntos.
6. Escriba un algoritmo que encuentre la distancia entre un par más cercano de puntos en una línea (recta).
7. Dé un ejemplo de la entrada para la cual comparar cada punto en la franja con los siguientes dos puntos produce una salida incorrecta.
8. Dé un ejemplo para demostrar que es posible colocar seis puntos en el rectángulo de la figura 13.1.2 cuando se incluye la base y se excluyen los otros lados.
9. Cuando se calculan las distancias entre un punto p en la franja y los puntos que le siguen, ¿se puede dejar de calcular las distancias desde p si se encuentra un punto q tal que la distancia entre p y q excede a δ? Explique su respuesta.
10. Demuestre que hay cuando mucho seis puntos en el rectángulo de la figura 13.1.2 cuando se incluye la base y los otros lados se excluyen.
11. Escriba un algoritmo (n lg n) que encuentre la distancia δ entre un par más cercano y que, si δ>0, también encuentre todos los pares que están a una distancia δ.
12. Escriba un algoritmo (n lg n) que encuentre la distancia δ entre un par más cercano y todos los pares que están a menos de 2δ.
13. Escriba un algoritmo (n lg n) que encuentre la distancia δ entre un par más cercano y todos los pares a menos de 2δ, donde cada par que está a menos de 2δ se lista exactamente una vez.
14. Explique por qué el siguiente algoritmo no encuentra la distancia δ entre un par más cercano y todos los pares a menos de 2δ.
ejercicio14(p, n) {
δ =par_más_cercano(p, n)
for i=1 to n−1
for j=i+1 to mín{n, i+31}
if (dist(pi, pj) < 2*δ)
println(i+“ ” +j)
}
15. Escriba un algoritmo que combine encontrar los puntos en la franja y buscar en la franja. De esta manera, el tamaño de la franja cambia en forma dinámica de modo que, en general, esta versión verifica menos puntos en la franja que el algoritmo 13.1.2.
16. Suponga que la distancia entre un par más cercano en un conjunto de n puntos en el plano es δ>0. Demuestre que el número de pares que están exactamente a una distancia δ es O(n).
