Chambers, Erin ;
Kostitsyna, Irina ;
Löffler, Maarten ;
Staals, Frank
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 NPhard. 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:127:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770156},
ISSN = {18688969},
year = {2016},
volume = {57},
editor = {Piotr Sankowski and Christos Zaroliagis},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6378},
URN = {urn:nbn:de:0030drops63783},
doi = {10.4230/LIPIcs.ESA.2016.27},
annote = {Keywords: trajectory analysis, representative trajectory, homotopy area}
}
2016
Keywords: 

trajectory analysis, representative trajectory, homotopy area 
Seminar: 

24th Annual European Symposium on Algorithms (ESA 2016)

Issue date: 

2016 
Date of publication: 

2016 