Trajectory Analysis: Bridging Algorithms and Visualization

Smaller and cheaper tracking devices with at the same time higher accuracy allow researchers to track large numbers of individuals to in their quest to understand the phenomena behind movement. The availability of this technology led to the continuing trend to collect, publish, and share movement datasets in data repositories. Because movement is ubiquitous, researchers from various disciplines are involved in tracking individuals, analyzing their trajectories, and ultimately, understanding the connection between movement and its drivers.

Methods to analyze these datasets have been developed in a variety of research areas. For example, researchers in algorithms are concerned with analyzing geometric problems and designing new algorithms for trajectory data, and visualization researchers develop novel visual representations from trajectory data to gain insights. Domain experts, from ecology, urban planning, or sports analytics, need new analytical methods for both: methods to quantify spatio-temporal properties and means to analyze movement data qualitatively, for instance exploration. To date, new methods in algorithms and visual ization are being developed only within their field. However, both algorithms and visualization are crucial and complement each other in the analysis of movement data.

In this thesis, we explore how combining algorithms and visualization can enhance the analysis of movement data. Thus, we aim to fill the methodological gap between algorithms and visualization by integrating computations, their context, and their visual representations more closely. Filling this gap will help movement analysts to externalize their cognition by integrating algorithmic means, visual means, and their domain knowledge into a holistic tooling. The contributions of this thesis make it possible for movement analysts to benefit from the exchange of ideas and concepts between algorithms and visualization.

Our contributions to the analysis of movement are manifold. We provide a thorough overview of the state-of-the-art in movement analysis in which we survey results to computational movement analysis as well as advances in the visualization of movement. We present a new taxonomy for the analysis of trajectory data, that can aid researchers in designing new analytical methods.

The second contribution of this thesis are results on the computational complexity of movement analysis tasks. We present two new lower bounds. We show that a simplification cannot be computed in subquadratic time for a trajectory of n points, presuming those points lie in Ω(log n) dimensions and assuming the Strong Exponential Time Hypothesis. Then, we prove that the discrete Fréchet distance for k trajectories, each of length n, cannot be computed in O(n^{k-eps}) time for any eps > 0 assuming the Strong Exponential Time Hypothesis. Furthermore, we provide an overview of previous results on algorithms and their algorithmic complexity for analyzing movement data.

Subsequently, we present a new algorithm to compute progressive simplifications, i.e., a series of simplifications that are consistent across multiple scales, in O(n^3 m) time with n as the number of points in the input curve and m as the number of scales. Progressive simplifications are particularly important for showing trajectories (or other line features) on interactive, zoomable maps. Our algorithm computes a progressive simplification for a range of continuous scales in O(n^5) time. A core element in simplification algorithms is the so-called shortcut graph. It stores for any line segment whether the segment approximates its induced subcurve given an error value. Moreover, we developed a new representation for such shortcut graphs allowing us to compute (non-)progressive simplifications more efficiently: a technique for computing the maximum error for all shortcuts in O(n^2 log n) time instead of O(n^3) time, and a compressed shortcut graph allowing us to find shortest paths typically in O(n log n) time.

Our fourth contribution in this thesis is a versatile visual analytics tool to explore interaction events as action-reaction patterns between two (or three) trajectories. We use alignment methods that allow us to capture delayed responses; we visualize these delays in addition to statistics on the alignment. Furthermore, we present a novel approach for computing a global delay between two trajectories, each of consisting of n points, in O(n log n) time, by employing Fast Fourier Transforms. We applied our approach to three different datasets and compared it to existing approaches on dynamic interaction.

The final contribution of this thesis is a visual analytics approach that helps ecologists to explore animal migration patterns interactively. We identify and aggregate stopovers, which are breaks from migration. The aggregation is visualized on top of a geographic map for varying spatial scales in addition to interconnected views to explore spatio-temporal events. We evaluated our approach with an expert user on a dataset of 75 lesser black-backed gulls.