1
$\begingroup$

I have a set of records (2 or more for each person) on multiple peoples locations (latitude and longitude) with timestamps. each record has: person ID, latitude, longitude, timeStamp. for each 2 people I wish to know if they have been under distance d from one another for over time t.

Is there an algorithm that can help me? Thanks!

$\endgroup$
2
  • $\begingroup$ Can you solve this problem if you want to know whether those two people have been less than distance $d$ away at any one point in time? What are you assuming about people's locations during times that are not covered by any record? $\endgroup$
    – D.W.
    Commented Apr 10, 2022 at 1:51
  • $\begingroup$ Yes I can. I'll just compare matching timestamps. But here I'm assuming same location untill another record with an updated timestamp says otherwise. $\endgroup$
    – Bob
    Commented Apr 10, 2022 at 2:01

1 Answer 1

1
$\begingroup$

Sort the records for each person, by increasing timestamp. Given a pair of people, you can merge the sorted list of records for each of those two people, and then do a linear scan over that sorted list of records: basically, once the two are within distance d, you start counting, and you check whether the remain within distance d for the next items until after t time steps have passed. To find this for all pairs of people, you can enumerate over all pairs of people and do a linear scan for each pair. There may be more efficient algorithms, but this is a very simple technique that will be easy to implement.

If you want a more efficient algorithm, here is an alternative. Imagine a metronome that "ticks" once every t/2 time steps. At each "tick" of the metronome, take the current location of all the people, and find all pairs of people who are within distance d of each other at that "tick". For each such pair, apply the method above to see if they have remained within distance d for a time period surrounding that tick. How can you efficiently find all pairs within distance d at a particular "tick"? Well, you have n points in the plane, and you want to find all pairs that are distance d or less apart. A simple approach is to grid the plane up into cells, each of size dxd, map each person's location into one cell, and then for each person, check for all other people in the same cell or in an adjacent cell, and for each pair of people you find in this way, check whether they are distance d apart.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.