How to find if location points set contains points with distance larger than 1 km

Question

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?

Answer 1

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:

• http://www.tcs.fudan.edu.cn/rudolf/Courses/Algorithms/Alg_ss_07w/Webprojects/Qinbo_diameter/2d_alg.htm
• http://cgm.cs.mcgill.ca/~athens/cs507/Projects/2000/MS/diameter/node2.html

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.