Data structures for Fréchet queries in trajectory data

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)
123 Downloads (Pure)


Let π be a trajectory in the plane, represented as a polyline with n edges. We show how to preprocess π into a data structure such that for any horizontal query segment σ in the plane and a subtrajectory between two vertices of π, one can quickly determine the Fréchet distance between σ and that subtrajectory. We provide data structures for these queries that need O(n2 log2 n) preprocessing time, O(n2 log2 n) space, and O(log2 n) query time. If we are interested only in the Fréchet distance between the complete trajectory π and a horizontal query segment σ, we can answer these queries in O(log2 n) time using only O(n2) space. Compilation copyright © 2017 Michiel Smid Copyright of individual papers retained by authors.All right reserved.
Original languageEnglish
Title of host publicationCCCG 2017 - 29th Canadian Conference on Computational Geometry, Proceedings 2017
Number of pages6
Publication statusPublished - 2017
Event29th Canadian Conference on Computational Geometry (CCCG 2017) - Ottawa, Canada
Duration: 26 Jul 201728 Jul 2017
Conference number: 29


Conference29th Canadian Conference on Computational Geometry (CCCG 2017)
Abbreviated titleCCCG 2017
Internet address


Dive into the research topics of 'Data structures for Fréchet queries in trajectory data'. Together they form a unique fingerprint.

Cite this