Given n points, how can I find the number of points with given distance

Question

I have an input of n unique points (X,Y) that are between 0 and 2^32 inclusive. The coordinates are integers.

I need to create an algorithm that finds the number of pairs of points with a distance of exactly 2018.

I have thought of checking with every other point but it would be O(n^2) and I have to make it more efficient. I also thought of using a set or a vector and sort it using a comparator based on the distance with the origin point but it wouldn't help at all.

So how can I do it efficiently?

Answer 1

You could try using a Quadtree. First you start sorting your points into the quadtree. You should specify a lower limit for the cell size of e.g. 2048 wich is a power of 2. Then iterate though the points and calculate distances to the points in the same cell and to the points in adjacent cells. That way you should be able to decrease the number of distance calculations drastically.

The main difficulty will probably be implementing the tree structure. You also have to find a way to find adjacent cells (you must include the possibility to traverse upwards in the tree)

The complexity of this is probably O(n*log(n)) in the best case but don't pin me down on that.

One additional word on the distance calculation: You are probably much faster if you don't do

dx = p1x - p2x;
dy = p1y - p2y;
if ( sqrt(dx*dx + dy*dy) == 2018 ) {
    ...
}

but

dx = p1x - p2x;
dy = p1y - p2y;
if ( dx*dx + dy*dy == 2018*2018 ) {
    ...
}

Squaring is faster than taking the sqare root. So just compare the square of the distance with the square of 2018.