Homotopy Measures for Representative Trajectories

Abstract

An important task in trajectory analysis is defining a meaningful representative for a cluster of similar trajectories. Formally defining and computing such a representative \(r\) is a challenging problem. We propose and discuss two new definitions, both of which use only the geometry of the input trajectories. The definitions are based on the homotopy area as a measure of similarity between two curves, which is a minimum area swept by all possible deformations of one curve into the other. In the first definition we wish to minimize the maximum homotopy area between \(r\) and any input trajectory, whereas in the second definition we wish to minimize the sum of the homotopy areas between \(r\) and the input trajectories. For both definitions computing an optimal representative is NP-hard. However, for the case of minimizing the sum of the homotopy areas, an optimal representative can be found efficiently in a natural class of restricted inputs, namely, when the arrangement of trajectories forms a directed acyclic graph.

Corresponding Publications

  • Homotopy Measures for Representative Trajectories

    Erin Chambers, Irina Kostitsyna, Maarten Löffler, Frank Staals

    Proc. 24th European Symposium on Algorithms, 2016
    @inproceedings{homotopymeasures2016,
      author = {Chambers, Erin and Kostitsyna, Irina and L{\"o}ffler, Maarten
                     and Staals, Frank},
      title = {Homotopy Measures for Representative Trajectories},
      booktitle = {Proc. 24th European Symposium on Algorithms},
      year = {2016},
      location = {Aarhus, Denmark},
      numpages = {17},
      pages = {27:1--27:17},
      keywords = {trajectories, representative, median, homotopy area},
      category = {trajectories},
      series = {Leibniz International Proceedings in Informatics (LIPIcs)},
      publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
      volume = {57},
      editor = {Piotr Sankowski and Christos Zaroliagis},
      doi = {10.4230/LIPIcs.ESA.2016.27},
      url = {https://dx.doi.org/10.4230/LIPIcs.ESA.2016.27},
    }
    
  • Homotopy Measures for Representative Trajectories

    Chambers Erin, Irina Kostitsyna, Maarten Löffler, Frank Staals

    Abstr. 31th European Workshop on Computational Geometry (EuroCG), 2015
    @article{homotopymeasures_eurocg2015,
      author = {Chambers Erin and Kostitsyna, Irina and L{\"o}ffler, Maarten and Staals, Frank},
      title = {Homotopy Measures for Representative Trajectories},
      journal = {Abstr. 31th European Workshop on Computational Geometry (EuroCG)},
      year = {2015},
      location = {Ljubljana, Slovenia},
      numpages = {4},
      pages = {125 -- 128},
      url = {http://eurocg15.fri.uni-lj.si/pub/eurocg15-book-of-abstracts.pdf},
      category = {trajectories},
      project = {homotopymeasures2016},
    }