| |
Buchin, M., Driemel, A., van Kreveld, M., & Sacristán, V. (2010). An algorithmic framework for segmenting trajectories based on spatio-temporal criteria. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems (pp. 202–211). Gis 2010. ACM.
Abstract: In this paper we address the problem of segmenting a trajectory such that each segment is in some sense homogeneous. We formally define different spatio-temporal criteria under which a trajectory can be homogeneous, including location, heading, speed, velocity, curvature, sinuosity, and curviness. We present a framework that allows us to segment any trajectory into a minimum number of segments under any of these criteria, or any combination of these criteria. In this framework, the segmentation problem can generally be solved in O(n log n) time, where n is the number of edges of the trajectory to be segmented.
|
|
|
Buchin, K., Buchin, M., Kreveld, M. van, Löffler, M., Silveira, R. I., Wenk, C., et al. Median Trajectories. Algorithmica, .
|
|
Buchin, K., Buchin, M., Kreveld, M. van, Löffler, M., Silveira, R. I., Wenk, C., et al. (2010). Median Trajectories. In Proc. 18th Annual European Symposium on Algorithms (ESA) (pp. 463–474). Lecture Notes in Computer Science, 6346. Springer.
Abstract: 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.
|
|
Buchin, K., Buchin, M., Gudmundsson, J., Löffler, M., & Luo, J. (2008). Detecting Commuting Patterns by Clustering Subtrajectories. In Proc. 19th International Symposium on Algorithms and Computation (ISAAC). LNCS, volume 5369 (pp. 644–655).
Abstract: In this paper we consider the problem of detecting commuting patterns in a trajectory. For this we search for similar subtrajectories. To measure spatial similarity we choose the Fréchet distance and the discrete Fréchet distance between subtrajectories, which are invariant under differences in speed. We give several approximation algorithms, and also show that the problem of finding the “˜longest” subtrajectory cluster is as hard as MaxClique to compute and approximate.
|
|
Buchin, K., Buchin, M., & Gudmundsson, J. (2010). Constrained Free Space Diagrams: a Tool for Trajectory Analysis. IJGIS, 24(7), 1101–1125.
Abstract: Time plays an important role in the analysis of moving object data. For many applications it is neither sufficient to only compare objects at exactly the same times, nor to consider only the geometry of the trajectories. We show how to leverage between these two approaches by extending a tool from curve analysis, the free space diagram. Our approach also allows to take further attributes of the objects like speed or direction into account. We demonstrate the usefulness of the new tool by applying it to the problem of detecting single file movement. A single file is a set of moving entities, which are following each other, one behind the other. This is the first algorithm for detecting this movement pattern. For this application, we analyse and demonstrate the performance of our tool both theoretically and experimentally.
|
|
|
