0

I have a set of users, each user has a set of points (n~5000) represented by latitude and longitude. I need to find static users. By 'static' I mean users for which there are no pairs of points further than 1km apart. What is the best algorithm for this?

AndrewS
  • 8,196
  • 5
  • 39
  • 53
user429400
  • 3,145
  • 12
  • 49
  • 68

1 Answers1

2

The maximum distance between any pair of points in a set of points is called the diameter of the set.

Here is one efficient algorithm, based on the convex hull, for solving this problem:

Since you probably don't care about exactness here, it would be easier to just find the minimum and maximum latitude and longitude over all of the points, and test whether a side of the box defined by these extrema is larger than some threshold. This works assuming you don't care about users near the north or south pole.

nibot
  • 14,428
  • 8
  • 54
  • 58
  • Thx :) Can you pls elaborate on the second alg. I'm not sure I understand why is it correct to calculate the side of the box and assume it is a good approximation..Any chance that you meant I should calculate the diagonal? (I guess not, I'm just trying to understand) – user429400 May 13 '14 at 20:01
  • Well, the diagonal of a square box is just sqrt(2) times the length of a side. So assuming you don't care about factors of around 50%, it just doesn't matter. – nibot May 13 '14 at 20:11