## New Results on Trajectory Grouping under Geodesic Distance

We study grouping of entities moving amidst obstacles, extending the recent work of Kostitsyna *et al.* We present an alternative algorithm that can compute the Reeb-graph, a graph which captures when and how the partition of the entities into groups changes, when the entities move amidst arbitrary polygonal obstacles. Our new algorithm is significantly faster than the algorithm of Kostitsyna et al. when the number of entities is significantly larger than the total complexity of the obstacles. Furthermore, we consider a restricted setting in which the obstacles are big compared to *ε*: the parameter determining when entities are close enough together to be in the same group. We show that in this setting the Reeb-graph is much smaller, and we can compute it much faster, than in the case of general obstacles.

keywords: Computational Geometry, Geographical Information Analysis, Trajectories

### Workshop or Poster (weakly reviewed)

Frank Staals, Jérôme Urhausen, Maarten Löffler

New Results on Trajectory Grouping under Geodesic Distance

Proc. 32nd European Workshop on Computational Geometry

11–14, 2016

back to list