One important pattern analysis task for trajectory data is to find a group: a set of entities that travel together over a period of time. In this paper, we compare four definitions of groups by conducting extensive experiments using various data sets. The grouping definitions are different by one or more of three different characteristics: whether they use the measured sample points or the continuous movement, how distance is used to decide if entities are in the same group, and whether the duration of the group is measured cumulatively or as one contiguous time interval. We are interested in the differences between the definitions and comparisons to human annotated data, if available. We concentrate on pedestrian data and on different crowd densities. Furthermore, we analyze the robustness of the definitions and their dependence on different sampling rates. We use two different types of trajectory data sets: synthetic trajectories from a crowd simulation model, and real-life trajectories extracted from video surveillance. We present the results of the quantitative evaluations. For experiments with real-life trajectories, we augment them with a qualitative evaluation using videos that show groups in the trajectories with a color coding.

We revisit the classical polygonal line simplification problem and study it using the Hausdorff distance and Fréchet distance. Interestingly, no previous authors studied line simplification under these measures in its pure form, namely: for a given epsilon>0, choose a minimum size subsequence of the vertices of the input such that the Hausdorff or Fréchet distance between the input and output polylines is at most epsilon. We analyze how the well-known Douglas-Peucker and Imai-Iri simplification algorithms perform compared to the optimum possible, also in the situation where the algorithms are given a considerably larger error threshold than epsilon. Furthermore, we show that computing an optimal simplification using the undirected Hausdorff distance is NP-hard. The same holds when using the directed Hausdorff distance from the input to the output polyline, whereas the reverse can be computed in polynomial time. Finally, to compute the optimal simplification from a polygonal line consisting of n vertices under the Fréchet distance, we give an O(kn^5) time algorithm that requires O(kn^2) space, where k is the output complexity of the simplification.

We consider the problem of testing, for a given set of planar regions R and an integer k, whether there exists a convex shape whose boundary intersects at least k regions of R. We provide polynomial-time algorithms for the case where the regions are disjoint axis-aligned rectangles or disjoint line segments with a constant number of orientations. On the other hand, we show that the problem is NP-hard when the regions are intersecting axis-aligned rectangles or 3-oriented line segments. For several natural intermediate classes of shapes (arbitrary disjoint segments, intersecting 2-oriented segments) the problem remains open.

One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al. [JoCG, 2015] introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments. We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R^1, specified by linear interpolation in a sequence of tau time stamps, we show that all maximal groups can be computed in O(tau^2 n^4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of alpha(n) in the running time. In higher dimensions, we can compute all maximal groups in O(tau^2 n^5 log n) time (for any constant number of dimensions). We also show that one tau factor can be traded for a much higher dependence on n by giving a O(tau n^4 2^n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on n and linear dependence on tau.

For a set of "similar" trajectories, a median trajectory is a trajectory that is most like the trajectories in the set, but it need not be a trajectory from the set itself. A recent method composed a median from parts of the set of trajectories, using ideas from homotopy to decide which parts to use. That method has two drawbacks. Firstly, it requires a significant subset of the trajectories to be homotopic, and such a subset may not always exist. Secondly, it sometimes misses relevant parts of trajectories because homotopy does not characterize the shape of the trajectories in all situations. In this paper we present a new approach to overcome these two drawbacks, leading to majority medians. We give results from extensive experiments, which indicate that majority medians are indeed better than homotopic medians.

We investigate the concept of a median among a set of trajectories. We establish criteria that a “median trajectory” should meet, and present two different methods to construct a median for a set of input trajectories. The first method is very simple, while the second method is more complicated and uses homotopy with respect to sufficiently large faces in the arrangement formed by the trajectories. We give algorithms for both methods, analyze the worst-case running time, and show that under certain assumptions both methods can be implemented efficiently. We empirically compare the output of both methods on randomly generated trajectories, and analyze whether the two methods yield medians that are according to our intuition. Our results suggest that the second method, using homotopy, performs considerably better.