In http://en.wikipedia.org/wiki/Closest_pair_of_points_problem possiamo vedere che menziona che è al massimo 6 punti che è più vicino al punto sull'altra metà, che può essere rappresentato come grafico seguente: 
vicina coppia di punti
My la domanda è per il punto P1 e il punto P2, la distanza dal punto rosso supererà sqrt (2) * d, perché fa parte della soluzione? Perché non è al massimo 4 punti che è più vicino a P piuttosto che al massimo 6 punti? Grazie.
P1 e P2 non sono parte della soluzione, ma devono essere esaminati sulla strada per la soluzione, poiché l'algoritmo esamina tutti i punti nella scatola, e P1 e P2 sono nella scatola.
noti che tale punto come Q può esistere, perché per ipotesi la distanza minima tra i punti nella metà destra del diagramma è d.
A cura di aggiungere: ti sembra di pensare che l'articolo di Wikipedia sta facendo una richiesta del genere:
Questa affermazione sarebbe falsa. Ma l'articolo non fa una tale affermazione. Invece, fa due domande distinte, che sono entrambi vero:
siamo solo contando il numero massimo di punti che possono trovarsi nel giusto d x 2d rettangolo. Poiché qualsiasi due punti è vincolato per avere una distanza minima di d, possiamo posizionare al massimo 6 punti nel rettangolo mentre soddisfiamo questo vincolo, come mostrato nella figura.
noti che i punti sul lato destro che si trovano a distanza d da P voglia trovano tutti all'interno di un segmento circolare di un cerchio centrato in P ed il cui raggio è d. Possono esserci al massimo 4 punti in questo segmento. Tuttavia, trovare il numero di punti all'interno di un segmento è più complicato rispetto alla ricerca del numero di punti all'interno di un rettangolo. Quindi usiamo il rettangolo invece e incorrere in un costo aggiuntivo di dover cercare al massimo 2 punti aggiuntivi.
Possiamo forse mostrare un esempio di esattamente 6 punti? – william007
No, non è possibile avere 6 punti che si trovano entro la distanza d da P. Ho modificato il post per renderlo più chiaro. Spero che questo ti aiuti. – krjampani
il limite è importante solo per la stima della complessità. Per quanto riguarda il codice, è possibile eseguire la scansione su e giù all'interno della distanza dRmin. Il limite qui suggerisce che al massimo vedrai 6 punti in ciascuna di queste scansioni, rendendo questo O (1).
Possiamo forse mostrare un esempio di esattamente 6 punti? – william007
Possiamo forse mostrare un esempio di esattamente 6 punti? – william007
Verifica se la mia modifica rende le cose più chiare per te. –
Grazie, se "Ci possono essere fino a 6 punti sul lato destro della linea che si trovano a una distanza d di P." è falso, qual è il numero corretto di punti? Se è inferiore a 6 punti, possiamo esaminare solo 5 punti? – william007