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

user_18037640 0
Viewed 308

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?

coordinates distance sorting algorithm c++
2 Answers

There is one Pythagorean triple with the hypotenuse of 2018: 11182+16802=20182.

Since all coordinates are integers, the only possible differences between the coordinates (both X an Y) of the two points are 0, 1118, 1680, and 2018.

Finding all pairs of points with a given difference between X (or Y) coordinates is a simple n log n operation.

Numbers other than 2018 might need a bit more work because they might be members of more than one Pythagorean triple (for example 2015 is a hypotenuse of 3 triples). If the number is not given as a constant, but provided at run time, you will have to generate all triples with this hypotenuse. This may require some sqrt(N) effort (N is the hypotenuse, not the number of points). One can find a recipe on the math stackexchange, e.g. here (there are many others).

user_7758060

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)

quadtree_image

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.

user_178623710
Related