Document Open Access Logo

Homotopy Measures for Representative Trajectories

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.ESA.2016.27.pdf
  • Filesize: 1 MB
  • 17 pages

Document Identifiers

Subject Classification

Keywords
  • trajectory analysis
  • representative trajectory
  • homotopy area

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Erin Chambers, Irina Kostitsyna, Maarten Löffler, and Frank Staals. Homotopy Measures for Representative Trajectories. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 27:1-27:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.27

Author Details

Erin Chambers
Irina Kostitsyna
Maarten Löffler
Frank Staals

References

  1. Pankaj K. Agarwal, Mark de Berg, Jie Gao, Leonidas J. Guibas, and Sariel Har-Peled. Staying in the middle: Exact and approximate medians in R¹ and R² for moving points. In CCCG, pages 43-46, 2005. Google Scholar
  2. Riddhipratim Basu, BhaswarB. Bhattacharya, and Tanmoy Talukdar. The projection median of a set of points in R^d. Discrete &Computational Geometry, 47(2):329-346, 2012. Google Scholar
  3. Kevin Buchin, Maike Buchin, Joachim Gudmundsson, Maarten Löffler, and Jun Luo. Detecting commuting patterns by clustering subtrajectories. IJCGA, 21(03):253-282, 2011. URL: http://dx.doi.org/10.1142/S0218195911003652.
  4. Kevin Buchin, Maike Buchin, Marc Kreveld, Maarten Löffler, RodrigoI. Silveira, Carola Wenk, and Lionov Wiratma. Median trajectories. Algorithmica, 66(3):595-614, 2013. URL: http://dx.doi.org/10.1007/s00453-012-9654-2.
  5. Erin W. Chambers and David Letscher. On the height of a homotopy. In CCCG, pages 103-106, 2009. Google Scholar
  6. Erin Wolf Chambers and Mikael Vejdemo-Johansson. Computing minimum area homologies. Computer Graphics Forum, 2014. URL: http://dx.doi.org/10.1111/cgf.12514.
  7. Erin Wolf Chambers and Yusu Wang. Measuring similarity between curves on 2-manifolds via homotopy area. In Proc. 29th Ann. Symp. on CG, pages 425-434. ACM, 2013. URL: http://dx.doi.org/10.1145/2462356.2462375.
  8. Erin Wolf Chambers, Éric Colin de Verdière, Jeff Erickson, Sylvain Lazard, Francis Lazarus, and Shripad Thite. Homotopic fréchet distance between curves or, walking your dog in the woods in polynomial time. CG, 43(3):295-311, 2010. URL: http://dx.doi.org/10.1016/j.comgeo.2009.02.008.
  9. Timothy M Chan. On levels in arrangements of curves, iii: further improvements. In Proc. of the 24th annual symposium on Computational geometry, pages 85-93. ACM, 2008. Google Scholar
  10. Stephane Durocher and David Kirkpatrick. The projection median of a set of points. CG, 42(5):364-375, 2009. Google Scholar
  11. S. Gaffney, A. Robertson, P. Smyth, S. Camargo, and M. Ghil. Probabilistic clustering of extratropical cyclones using regression mixture models. Climate Dynamics, 29(4):423-440, 2007. Google Scholar
  12. S. Gaffney and P. Smyth. Trajectory clustering with mixtures of regression models. In Proc. 5th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, pages 63-72, 1999. Google Scholar
  13. Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, and Anastasios Sidiropoulos. How to walk your dog in the mountains with no magic leash. In Proc. 28th Ann. Symp. on CG, pages 121-130. ACM, 2012. URL: http://dx.doi.org/10.1145/2261250.2261269.
  14. Allen Hatcher. Algebraic Topology. Cambridge University Press, 2001. URL: http://www.math.cornell.edu/~hatcher/.
  15. Donald E. Knuth and Arvind Raghunathan. The problem of compatible representatives. SIAM Journal on Discrete Mathematics, 5(3):422-427, 1992. URL: http://dx.doi.org/10.1137/0405033.
  16. J.G. Lee, J. Han, and K.Y. Whang. Trajectory clustering: a partition-and-group framework. In Proc. ACM SIGMOD Int. Conf. on Management of Data, pages 593-604, 2007. Google Scholar
  17. David Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982. URL: http://dx.doi.org/10.1137/0211025.
  18. James R. Munkres. Topology. Prentice-Hall, 2nd edition, 2000. Google Scholar
  19. M. Vlachos, D. Gunopulos, and G. Kollios. Discovering similar multidimensional trajectories. In Proc. 18th Int. Conf. Data Engin., pages 673-684, 2002. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact