I am looking for an efficient way of computing if two objects could have encountered. The data that describes that object movement (trajectory) are represented using x and y coordinates and timestamp. An encounter is described as spatio-temporal proximity. That is, two objects are d meters away in the window of t seconds for some given d and t. I have a large database of trajectories of different objects, where some data is sparser than the other.
What is the best algorithm to compute encounters and are there any Java/Scala libraries that would help?
Edit: Data describes movements of people. People may continuously walk, they may walk at different speeds and they may also stop. The data is represented only using x and y coordinates, timestamp and uid (id of a person). The data are only samples and are not the exact representation of trajectories; i.e. you should not assume that a person id moves from the point p1 (associated with the time stamp t1) in a straight line to the point p2(associated with the time stamp t2) at a speed distance(p1, p2) / (t2 - t1), where t1 and t2 are two chronologically consecutive time stamps. Furthermore, the positions of people are not sampled at uniform rate.