Algoritmo del "par de puntos más cercano"

Question

Tengo un problema para entender por qué sólo tengo que considerar los siguientes 7 puntos en el

Algoritmo del par de puntos más cercano .

¿Puede alguien explicarlo con más detalle?

Answer 1

¿Cuál puede ser el problema?

Con SW1 abierto, el camino para la corriente de la base del emisor de Q2 es a través de R2, D1 y R3.

¿Alguna idea de cómo puedo solucionarlo?

El circuito anterior utiliza un transistor menos, pero consume más del doble de energía cuando L1 está encendido que cuando L2 está encendido. Sería sencillo añadir otro transistor y una resistencia para "arreglar" eso. El valor de R3 debe determinarse experimentalmente.

Answer 2

Se explica debajo del título "Corrección". Como máximo 8 puntos pueden residir en el $\delta \times 2\delta$ rectángulo porque como máximo se pueden encontrar 4 en el cuadrado de la izquierda y como máximo se pueden encontrar 4 en el cuadrado de la derecha. Con 8 puntos en total, basta con comprobar que hay 7 puntos en la matriz $Y'$ . El fondo de la prueba es complicado y se describe en la página que mencionas.

Answer 3

Hay que entender dos cosas:

(1) La primera está bien descrita en el texto que has enlazado: Después de encontrar el par de puntos más cercano en el lado izquierdo (denota la distancia entre ellos por $\delta_L$ ), y el par de puntos más cercano en el lado derecho (denotando su distancia por $\delta_R$ ), sólo nos interesa saber si hay un par de puntos aún más cercanos, de los cuales uno se encuentra en el lado izquierdo y el otro en el lado derecho. Así que sólo nos interesan tales pares $(p_L, p_R)$ que son inferiores a $\delta=min(\delta_L, \delta_R)$ unidades de distancia. Así que la distancia entre $p_L$ y la línea $l$ (ver figura $(a)$ ) no debe ser superior a $\delta$ y la distancia entre $p_R$ y la línea $l$ no debe ser superior a $\delta$ . Es decir, basta con considerar únicamente los puntos situados en la franja vertical infinita que se muestra en la figura $(a)$ . Además, la distancia vertical entre $p_L$ y $p_R$ no debe ser superior a $\delta$ (esto se muestra en la figura $(b)$ ). Así, podemos filtrar primero todos los puntos que se encuentran fuera de la franja vertical (figura $(a)$ ). Entonces, recordando que tenemos los puntos ordenados según su $y$ coordenada, vemos que basta con considerar para cada punto, todos los puntos anteriores hasta encontrar un punto más de $\delta$ unidades de distancia en vertical. ¿Cuántos puntos podríamos comprobar hasta que esto ocurra? Esto está limitado desde arriba por el doble del número máximo de puntos en un $\delta \times \delta$ bajo la restricción de que ningún punto sea menor que $\delta$ unidades de distancia (recuerde que cada una de estas dos $\delta \times \delta$ cajas está totalmente contenida en el lado izquierdo o en el derecho, y recuerda cómo $\delta$ se definió). Entonces, ¿cuántos puntos es esto?

Esta es la segunda parte a entender, que en realidad no se demuestra en el texto que enlazaste: (2) El número máximo de puntos en un $\delta \times \delta$ caja, tal que cualquier par de puntos es al menos $\delta$ unidades de distancia es como máximo 4. La prueba es fácil: Dividir la caja en 4 cajas, cada una de tamaño $\delta/2 \times \delta/2$ . El diámetro de cada una de estas cajas es $\sqrt{2}\delta/2$ que es menor que $\delta$ . Por lo tanto, en cada una de esas cajas pequeñas puede haber a lo sumo un punto y, por lo tanto, hay a lo sumo 4 puntos en el $\delta \times \delta$ caja.