Computing longest duration flocks in trajectory data
Joachim Gudmundsson, Marc J. van Kreveld · 2006
Moving point object data can be analyzed through the discovery of patterns. We consider the computational efficiency of computing two of the most basic spatio-temporal patterns in trajectories, namely flocks and meetings. The patterns are large enough subgroups of the moving point objects that exhibit similar movement and proximity for a certain amount of time. We consider the problem of computing a longest duration flock or meeting. We give several exact and approximation algorithms, and also show that some variants are as hard as MaxClique to compute and approximate.