Reporting flock patterns (Q945937)

The authors discuss algorithms to detect flocks in moving objects. They start with a set of \(n\) identities in the plane and the position of the entities at time steps \(t_1,\dots, t_\tau\). It is supposed that these time steps are taken synchronously for all the identities and that the movement between the steps is linear at constant speed. Given integers \(m, k\) and \(r>0\), a \textit{flock} is a set of \(m\) entities such that during a \(k\)-length time, all of the entities belong to a (moving) ball of radious \(r\). The main problem is then how to detect all possible flocks from the data. The main idea of the article is, for each entity \(p\) and a \(k\)-length interval \([t_i,t_j]\), \(j-i+1\geq k\), let \((x_l,y_l)\) the possition of \(p\) at discrete time \(t_l\). Then consider the vector \((x_i,y_i,x_{i+1},y_{i+1},\dots,x_j,y_j)\) in a higher dimensional space. A flock is then a set of \(m\) entities whose corresponding vectors that are close in this higher space. In order to work with these objects, one has to be careful on how to describe the spatial objects, since the complexity increases exponentially in \(k\). The authors use a specific data structure called skip-quadtree. Some queries over these trees and operations can be done in constant time \(n\) for the model of computation assumed in the article. A set of different algorithms to compute flocks within this specific model is provided. These algorithms are approximate, they will correctly report all the flocks but there may be some detected fake-flocks, that are flocks for a radius \(\Delta r\), where \(\Delta\) may be \(\sqrt{8}+\varepsilon\) (the box method), \(2+\varepsilon\) (the pipe method) and \((1+\varepsilon)\) (ample-points method). After describing the algorithms and giving theoretical complexity, a brief discussion on related problems follows. Finally, there is a section of experiments where it is shown how the algorithms behave in practice under a number of different situations and some explanations and hypothesis of why the algorithms behave as they do.