Clustering trajectories is a central challenge when confronted with large amounts of movement data such as full-body motion data or GPS data. We study a clustering problem that can be stated as a geometric set cover problem: Given a polygonal curve of complexity , find the smallest number of representative trajectories of complexity at most such that any point on the input trajectories lies on a subtrajectory of the input that has Fr\u00e9chet distance at most to one of the representative trajectories. This problem was first studied by Akitaya et al. (2021) and Br\u00fcning et al. (2022). They present a bicriteria approximation algorithm that returns a set of curves of size which covers the input with a radius of in time , where is the smallest number of curves of complexity needed to cover the input with a distance of . The representative trajectories computed by their algorithm are always line segments. In applications however, one is usually interested in representative curves of higher complexity which consist of several edges. We present a new approach that builds upon the works of Br\u00fcning et al. (2022) computing a set of curves of size in time with the same distance guarantee of , where each curve may consist of curves of complexity up to the given complexity parameter . To validate our approach, we conduct experiments on different types of real world data: high-dimensional full-body motion data and low-dimensional GPS-tracking data.<\/p>\n","protected":false},"excerpt":{"rendered":"
Clustering trajectories is a central challenge when confronted with large amounts of movement data such as full-body motion data or GPS data. We study a clustering problem that can be stated as a geometric set cover problem: Given a polygonal curve of complexity , find the smallest number of representative trajectories of complexity at most such that any point on the input trajectories lies on a subtrajectory of the input […]<\/p>\n","protected":false},"author":12,"featured_media":0,"template":"","meta":{"_acf_changed":false,"footnotes":""},"publication-type":[30],"class_list":["post-32804","publication","type-publication","status-publish","hentry","publication-type-article"],"acf":[],"publishpress_future_workflow_manual_trigger":{"enabledWorkflows":[]},"_links":{"self":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32804","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication"}],"about":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/types\/publication"}],"author":[{"embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/users\/12"}],"version-history":[{"count":0,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication\/32804\/revisions"}],"wp:attachment":[{"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/media?parent=32804"}],"wp:term":[{"taxonomy":"publication-type","embeddable":true,"href":"https:\/\/lamarr-institute.org\/de\/wp-json\/wp\/v2\/publication-type?post=32804"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}