Variazione più stretta dell'algoritmo di coppie di punti

Question

So che questo può essere un duplicato, ma sembra una variazione dell'algoritmo "Coppia di punti più vicina".

Dato un insieme di N punti (x, y) nel quadrato unitario e una distanza d Trovare tutti coppia di punti tale che la distanza tra di loro è al massimo d.

Per grandi N il metodo della forza bruta non è un'opzione. Oltre ai metodi 'sweep line' e 'divide and conquer', c'è una soluzione più semplice? Queste coppie di punti sono i bordi di un grafo non orientato, che ho bisogno di attraversarlo e dire se è collegato o meno (che ho già fatto usando DFS, ma quando N = 1 milione non finisce mai!).

Qualsiasi pseudocodice, commenti o idee sono i benvenuti, Grazie!

EDIT: Ho trovato questo su Sedgewick libro (sto guardando il codice in questo momento):

Programma 3.18 usa un array bidimensionale di liste concatenate per migliorare il tempo di esecuzione del Programma 3.7 per un fattore di circa 1/d2 quando N è sufficientemente grande. Divide l'unità in una griglia di quadrati più piccoli di uguali dimensioni. Quindi, per ogni quadrato, crea un elenco collegato di tutti i punti che cadono in quel quadrato. L'array bidimensionale offre la possibilità di accedere immediatamente allo insieme di punti vicini a un punto specifico; gli elenchi collegati offrono la flessibilità per memorizzare i punti in cui possono cadere senza che sia necessario sapere in anticipo quanti punti rientrano in ciascun riquadro della griglia.

Answer 1

Siamo davvero alla ricerca di punti all'interno di un cerchio di centro (x, y) e raggio d.

Il quadrato che racchiude il cerchio è un quadrato di centro (x, y) e lati 2d. Ogni punto fuori da questo quadrato non ha bisogno di essere controllato, è fuori. Quindi, un punto a (xa, ya) è fuori se abs (xa - x)> d o abs (ya -yb)> d.

Lo stesso per il quadrato che è allegato a da quel cerchio è un quadrato di centro (x, y) e diagonali 2d. Ogni punto fuori da questo quadrato non ha bisogno di essere controllato, è dentro. Quindi, un punto a (xa, ya) è in se abs (xa - x) < (d * 1.412) o abs (ya -yb) < (d * 1.412).

Queste due semplici regole combinate riducono molto il numero di punti da controllare. Se ordiniamo il punto con la loro x, filtriamo i possibili punti, ordiniamo con la loro y, arriviamo a quelli di cui abbiamo veramente bisogno per calcolare l'intera distanza.

Answer 2

Per un dato punto, è possibile utilizzare una euristica di Manhattan (x-delta più y-delta) per filtrare la maggior parte dei punti che non si trovano nella distanza "d" - filtrare tutti i punti la cui distanza Manhattan è maggiore di (sqrt (2) * d), quindi eseguire il test della distanza costosa e precisa sui punti rimanenti.