Perché confrontiamo al massimo 7 punti nell'algoritmo della coppia più vicina?

Question

Quindi, se entro δ * 2δ rettangolo R, abbiamo solo bisogno di confrontare un punto dal lato sinistro con 7 punti sul lato destro. Quello che non capisco è che, nonostante la lettura della dimostrazione, all'interno di R possiamo riempire il numero di punti che vogliamo all'interno del rettangolo che può superare il numero totale di 7. Immaginate di avere δ = 2, un punto p (1.2, 1.1) sul lato sinistro, e sul lato destro, abbiamo un intero gruppo di q, come q (1.5, 1.7), q (1.4, 1.3), ..... come può solo confrontare 7 punti rileva il coppia più vicina? Ho pensato che dobbiamo confrontare ogni punto nel rettangolo R, se è il caso. Mi aiuti per favore.

Answer 1

Ci possono essere solo 6 punti all'interno del rettangolo, poiché questo è il numero massimo di punti che è possibile inserire in un rettangolo con lati \ delta e 2 * \ delta mantenendo la proprietà che sono almeno \ delta distanti da ciascun altro.

Il modo di porre quei 6 punti è mostrato nella figura seguente:

È possibile controllare da sé che non c'è modo di mettere un altro punto all'interno del rettangolo senza violare la proprietà di distanza. Se aggiungi più di 6 punti, sarebbero meno di \ delta a parte, che è una contraddizione, dal momento che \ delta dovrebbe essere la distanza tra la coppia più vicina.

Poiché potrebbero esserci un massimo di 6 punti, il test 7 garantirà di trovare la soluzione.

Ho ottenuto la figura 1 da these UCSB slides, che può essere utile a voi.