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 \(\mathbb{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^42^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\).

Corresponding Publications

  • A Refined Definition for Groups of Moving Entities and its Computation

    Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

    Proc. 27th International Symposium on Algorithms and Computation, 2016
    Invited for a special issue on ISAAC 2016 in the International Journal on Computational Geometry and its Applications
    @inproceedings{refined_grouping2016,
      author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                     Wiratma, Lionov},
      title = {A Refined Definition for Groups of Moving Entities and its Computation},
      booktitle = {Proc. 27th International Symposium on
                     Algorithms and Computation},
      year = {2016},
      location = {Sydney, Australia},
      numpages = {12},
      isbn = {978-3-95977-026-2},
      issn = {1868-8969},
      keywords = {trajectories, grouping, moving entities},
      category = {trajectories},
      series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      volume = {64},
      editor = {Seok-Hee Hong},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      url = {https://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.48},
      doi = {10.4230/LIPIcs.ISAAC.2016.48},
      note = {Invited for a special issue on ISAAC 2016 in the International Journal on Computational Geometry and its Applications},
    }
    
  • A Refined Definition for Groups of Moving Entities and its Computation

    Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

    International Journal of Computational Geometry & Applications, 2018
    Special Issue on ISAAC 2016.
    @article{refined_grouping2018,
      author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                     Wiratma, Lionov},
      title = {A Refined Definition for Groups of Moving Entities and its Computation},
      journal = {International Journal of Computational Geometry \& Applications},
      category = {trajectories},
      project = {refined_grouping2016},
      year = {2018},
      volume = {28},
      number = {02},
      pages = {181--196},
      url = {https://dx.doi.org/10.1142/S0218195918600051},
      doi = {10.1142/S0218195918600051},
      note = {Special Issue on ISAAC 2016.},
    }
    
  • A Refined Definition for Groups of Moving Entities and its Computation

    Marc van Kreveld, Maarten Löffler, Frank Staals, Lionov Wiratma

    Abstr. 32th European Workshop on Computational Geometry (EuroCG), 2016
    @article{new_grouping_eurocg2016,
      author = {van Kreveld, Marc and L{\"o}ffler, Maarten and Staals, Frank and
                     Wiratma, Lionov},
      title = {A Refined Definition for Groups of Moving Entities and its Computation},
      journal = {Abstr. 32th European Workshop on Computational Geometry (EuroCG)},
      year = {2016},
      location = {Lugano, Switzerland},
      numpages = {4},
      category = {trajectories},
      project = {refined_grouping2016},
      url = {http://www.eurocg2016.usi.ch/sites/default/files/paper_67.pdf},
    }