Trajectory Grouping Structure under Geodesic Distance

Abstract

Due to GPS and related technology, trajectory data has become one of the main types of geographic data, and algorithmic tools to handle large quantities of such data are essential. A single trajectory is typically represented as a sequence of time-stamped points in the plane. In a collection of such trajectories one can identify groups of moving entities and merges and splits of such groups. This information can be summarized in the trajectory grouping structure. Extending the work of Buchin WADS 2013], we show that the trajectory grouping structure can be computed efficiently also if obstacles are present and the distance between the entities is measured by geodesic distance. We bound the number of critical events: times at which the distance between two subsets of moving entities is exactly $, where $ is the threshold distance until where two entities are close enough to be in one group. In case the entities move in a simple polygon we give an $O(tau n^2)$ upper bound, which is tight in the worst case. In case of well-spaced obstacles we give an $O(n^2 + m4(n)))$ upper bound, where $m$ is the total complexity of the obstacles, and $s(n)$ denotes the maximum length of a Davenport-Schinzel sequence of $n$ symbols of order $s$. In case of general obstacles we give an $O(n^2 + m^2 4(n)))$ upper bound. We also present lower bounds that show that these two upper bounds are close to optimal. Furthermore, for all cases we provide efficient algorithms to compute the critical events, which in turn leads to efficient algorithms to compute the trajectory grouping structure.