2026-07-23T16:36:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6378 2024-03-06T10:38:06Z ddc:004 open_access

Homotopy Measures for Representative Trajectories Chambers, Erin Kostitsyna, Irina Löffler, Maarten Staals, Frank trajectory analysis representative trajectory homotopy area 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Erin Chambers and Irina Kostitsyna and Maarten Löffler and Frank Staals 2016 Is Part Of LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2016.27 urn:nbn:de:0030-drops-63783 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.27 eng https://creativecommons.org/licenses/by/3.0/legalcode