An Improved Definition for Grouping Moving Entities and its Computation
We propose a new definition of a group of moving entities which corresponds better to human intuition in dense environments. For a set of n moving entities in ℝ1, specified by linear interpolation in a sequence of τ time steps, we show that all maximal groups can be computed in O(n4τ) time, which is worst-case optimal. The algorithm extends to higher dimensions.
keywords: Computational Geometry, Geographical Information Analysis, Trajectories
Conference Proceedings (peer-reviewed)
Frank Staals, Lionov Wiratma, Maarten Löffler, Marc van Kreveld
An Improved Definition for Grouping Moving Entities and its Computation
Proc. 27th International Symposium on Algorithms and Computation
(to appear), LIPIcs, 64, 48:1–48:12, 2016
Workshop or Poster (weakly reviewed)
Frank Staals, Lionov Wiratma, Maarten Löffler, Marc van Kreveld
An Improved Definition for Grouping Moving Entities and its Computation
Proc. 32nd European Workshop on Computational Geometry
15–18, 2016
back to list