c - Closest pair of points algorithm variation -

i know may duplicate, seems variation on 'closest pair of points' algorithm.

given set of n points (x, y) in unit square , distance d, find all pair of points such distance between them @ d.

for large n brute force method not option. besides 'sweep line' , 'divide , conquer' methods, there simpler solution? these pair of points edges of undirected graph, need traverse , if it's connected or not (which did using dfs, when n = 1 million never finishes!).

any pseudocode, comments or ideas welcome, thanks!

edit: found on sedgewick book (i'm looking @ code right now):

program 3.18 uses two-dimensional array of linked lists improve running time of program 3.7 factor of 1/d2 when n sufficiently large. divides unit square grid of equal-sized smaller squares. then, each square, builds linked list of points fall square. two-dimensional array provides capability access set of points close given point; linked lists provide flexibility store points may fall without our having know ahead of time how many points fall each grid square.

we looking points inside of circle of center (x,y) , radius d.

the square encloses circle square of center (x,y) , sides 2d. point out of square not need checked, it's out. so, point (xa, ya) out if abs(xa - x) > d or abs (ya -yb) > d.

same square enclosed circle square of center (x,y) , diagonals 2d. point out of square not need checked, it's in. so, point (xa, ya) in if abs(xa - x) < (d * 1.412) or abs(ya -yb) < (d * 1.412).

those 2 easy rules combined reduce lot number of points checked. if sort point x, filter possible points, sort y, come ones need calculate full distance.