## 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*(*n*^{4}*τ*) 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