par más cercano de los puntos

Question

En http://en.wikipedia.org/wiki/Closest_pair_of_points_problem podemos ver que menciona que es como máximo 6 puntos que está más cerca del punto de la otra mitad, que se puede representar como el siguiente gráfico:

Mi la pregunta es para el punto P1 y el punto P2, la distancia al punto rojo excederá sqrt (2) * d, ¿por qué es parte de la solución? ¿Por qué no hay a lo sumo 4 puntos lo más cercano a P en lugar de a lo sumo 6 puntos? Gracias.

Answer 1

P1 y P2 no son parte de la solución, pero tienen que ser examinadas en el camino a la solución, porque el algoritmo examina todos los puntos en la caja, y P1 y P2 son en el cuadro.

Tenga en cuenta que puede existir ningún punto como su Q, porque, por hipótesis, la distancia mínima entre puntos en la mitad derecha del diagrama es d.

Editado para agregar: usted parece pensar que el artículo de Wikipedia está haciendo una afirmación como esta:

• Puede haber un máximo de 6 puntos en el lado derecho de la línea que se encuentran dentro de una distancia d de P.

Este reclamo sería falso. Pero el artículo no hace tal afirmación. En su lugar, hace que dos reivindicaciones independientes, ambos de los cuales son verdaderas:

1. Todos los puntos en el lado derecho de la línea que se encuentran dentro de una distancia d de P están dentro de la caja.
2. Puede haber hasta 6 puntos en la caja.

Answer 2

Estamos contando solamente el número máximo de puntos que pueden estar en el rectángulo derecho d x 2d. Como dos puntos se limitan a tener una distancia mínima de d, podemos colocar como máximo 6 puntos en el rectángulo mientras se satisface esta restricción, como se muestra en la figura.

Tenga en cuenta que los puntos en el lado derecho que están a una distancia d de P deberían estar todos dentro de un segmento circular de un círculo centrado en P y cuyo radio es d. Puede haber como máximo 4 puntos en este segmento. Sin embargo, encontrar la cantidad de puntos dentro de un segmento es más complicado que encontrar la cantidad de puntos dentro de un rectángulo. Entonces, usamos el rectángulo e incurrimos en un costo adicional de tener que buscar como máximo 2 puntos adicionales.

Answer 3

La cota es sólo es importante para la estimación de la complejidad. En lo que respecta al código, puede escanear hacia arriba y hacia abajo dentro de la distancia dRmin. El límite aquí sugiere que, como mucho, verá 6 puntos en cada uno de esos escaneos, por lo que O (1).