License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2016.48
URN: urn:nbn:de:0030-drops-68188
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6818/
van Kreveld, Marc ;
Löffler, Maarten ;
Staals, Frank ;
Wiratma, Lionov
A Refined Definition for Groups of Moving Entities and its Computation
Abstract
One of the important tasks in the analysis of spatio-temporal data collected from moving entities is to find a group: a set of entities that travel together for a sufficiently long period of time. Buchin et al. [JoCG, 2015] introduce a formal definition of groups, analyze its mathematical structure, and present efficient algorithms for computing all maximal groups in a given set of trajectories. In this paper, we refine their definition and argue that our proposed definition corresponds better to human intuition in certain cases, particularly in dense environments.
We present algorithms to compute all maximal groups from a set of moving entities according to the new definition. For a set of n moving entities in R^1, specified by linear interpolation in a sequence of tau time stamps, we show that all maximal groups can be computed in O(tau^2 n^4) time. A similar approach applies if the time stamps of entities are not the same, at the cost of a small extra factor of alpha(n) in the running time. In higher dimensions, we can compute all maximal groups in O(tau^2 n^5 log n) time (for any constant number of dimensions).
We also show that one tau factor can be traded for a much higher dependence on n by giving a O(tau n^4 2^n) algorithm for the same problem. Consequently, we give a linear-time algorithm when the number of entities is constant and the input size relates to the number of time stamps of each entity. Finally, we provide a construction to show that it might be difficult to develop an algorithm with polynomial dependence on n and linear dependence on tau.
BibTeX - Entry
@InProceedings{vankreveld_et_al:LIPIcs:2016:6818,
author = {Marc van Kreveld and Maarten L{\"o}ffler and Frank Staals and Lionov Wiratma},
title = {{A Refined Definition for Groups of Moving Entities and its Computation}},
booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)},
pages = {48:1--48:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-026-2},
ISSN = {1868-8969},
year = {2016},
volume = {64},
editor = {Seok-Hee Hong},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6818},
URN = {urn:nbn:de:0030-drops-68188},
doi = {10.4230/LIPIcs.ISAAC.2016.48},
annote = {Keywords: moving entities, trajectories, grouping, computational geometry}
}
|
Keywords: |
|
moving entities, trajectories, grouping, computational geometry |
|
Collection: |
|
27th International Symposium on Algorithms and Computation (ISAAC 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
07.12.2016 |
