FINDING POPULAR PLACES
Marc Benkert, Bojan D. Djordjević, Joachim Gudmundsson, Thomas Wolle · International Journal of Computational Geometry & Applications · 2010
Widespread availability of location aware devices (such as GPS receivers) promotes capture of detailed movement trajectories of people, animals, vehicles and other moving objects. We investigate spatio-temporal movement patterns in large tracking data sets, i.e. in large sets of polygonal paths. Specifically, we study so-called 'popular places', that is, regions that are visited by many entities. Given a set of polygonal paths with a total of [Formula: see text] vertices, we look at the problem of computing such popular places in two different settings. For the discrete model, where only the vertices of the polygonal paths are considered, we propose an [Formula: see text] algorithm; and for the continuous model, where also the straight line segments between the vertices of a polygonal path are considered, we develop an [Formula: see text] algorithm. We also present lower bounds and hardness results.