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
  • 7,678
  • 3
  • 37
  • 53
user429400
  • 3,025
  • 12
  • 45
  • 66

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
  • 13,890
  • 7
  • 52
  • 57
  • 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