Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2016.27
URN: urn:nbn:de:0030-drops-63783
URL: https://drops.dagstuhl.de/opus/volltexte/2016/6378/
Chambers, Erin ; Kostitsyna, Irina ; Löffler, Maarten ; Staals, Frank
Homotopy Measures for Representative Trajectories
| pdf-format: |
|
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.
BibTeX - Entry
@InProceedings{chambers_et_al:LIPIcs:2016:6378,
author = {Erin Chambers and Irina Kostitsyna and Maarten L{\"o}ffler and Frank Staals},
title = {{Homotopy Measures for Representative Trajectories}},
booktitle = {24th Annual European Symposium on Algorithms (ESA 2016)},
pages = {27:1--27:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-015-6},
ISSN = {1868-8969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6378},
URN = {urn:nbn:de:0030-drops-63783},
doi = {10.4230/LIPIcs.ESA.2016.27},
annote = {Keywords: trajectory analysis, representative trajectory, homotopy area}
}
| Keywords: | trajectory analysis, representative trajectory, homotopy area | |
| Seminar: | 24th Annual European Symposium on Algorithms (ESA 2016) | |
| Issue date: | 2016 | |
| Date of publication: | 18.08.2016 |
