CODEWITHSUNDEEP
c++complexity-theorytime-complexityeuclidean-distance
Dan Dinu
Dan Dinu

Reputation: 33438

minimum distance between 2 points in c++

I'm given m places (x,y coordinates).

I have n requests of finding the closest place to a given point P(x,y); (The minimum Euclidian distance)

How can i solve this problem below O(n*m) where n is the number of requests and m the number of places? I could use squared Euclidian distances but it's still n*m.

Upvotes: 2

Views: 1898

Answers (3)

peakxu
peakxu

Reputation: 6675

Try a kd-tree. A high performance library implementation can be found here.

Note: I'm pointing you to an approximate nearest-neighbors search which is optimized for high dimensions. This may be slightly overkill for your application.

Edit:

For a 2d kd-tree, the build time would be O(m*log(m)) and the query time would be O(n*sqrt(m)). This should end up being a net win over the naive solution if your number of queries n, exceeds log(m).

The library means you don't have to implement it so the complexity shouldn't be an issue.

If you want to generalize to high dimension extremely fast querying, check out locality sensitive hashing.

Upvotes: 1

towi
towi

Reputation: 22347

The Nearest-Neighbor-Problem, eh? I found Robert Sedgewick Std Book very useful in these cases. He describes Nearest Neighbour Search, too.

Upvotes: 0

Pete Wilson
Pete Wilson

Reputation: 8704

Interesting. To reduce the effect of n, I wonder if perhaps it would help to save the result of each request as you encounter and handle it. A clever result table might shortcut the need to calculate sqrt( x2 + y2) in solving subsequent requests.

Upvotes: 0

Related Questions