0

Given a very large set of GPS coordinates, is there a time/computationally efficient way to determine whether an input GPS coordinate is within a given radius of any point in the set? Pre-computation is acceptable. The best I could think of is an O(N) implementation but just wondering if there is a better way to approach this problem.

nmock
  • 1,907
  • 2
  • 20
  • 29

3 Answers3

0

You should look into range tree. Preprocess the points to create the range tree and then use it search for all the points in a specific range. Space complexity is O(n log n). Time complexity is O(n log n + k) where k is the number of points in the search radius.

Harman
  • 1,571
  • 1
  • 19
  • 31
0

The given coordinate can be tested with time complexity slighlty above O(log4(N)) asuming a radius that is small compared to the space the points spread.

log4 is the logarithmus with base 4

A Quadtree works extremly well for this task.
An alternative is the R-Tree.

AlexWien
  • 28,470
  • 6
  • 53
  • 83
0

If you are looking for a Java implementation, you may try one of the KD-Trees I have fully posted here. With that you are able to find the nearest point to your new GPS input. Then you just need to check the real distance, for whether it is inside the radius you are interested or not.

Community
  • 1
  • 1
user2808624
  • 2,502
  • 14
  • 28
  • the nearest is not sufficent, he needs all points within a radius, not just the nearest. – AlexWien Aug 19 '15 at 18:06
  • How do you know? I can't read that from the question: "determine whether an input GPS coordinate is within a given radius of any point". That's just a yes or no question to me. – user2808624 Aug 20 '15 at 05:44
  • Then how many times you must search? Uisng your implemetaion of KD tree, he has to search N times, one for each point. It works, but it is N times higher than neccessary – AlexWien Aug 20 '15 at 10:55
  • I guess there is still some misunderstanding. If you have a number of known locations, and you just want to know for a new location, whether its nearby one of your known locations, you just need to search once. – user2808624 Aug 20 '15 at 19:19