Data structures for Fréchet queries in trajectory data

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

2 Citations (Scopus)
86 Downloads (Pure)

Abstract

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
Pages214-219
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
http://2017.cccg.ca/

Conference

Conference29th Canadian Conference on Computational Geometry (CCCG 2017)
Abbreviated titleCCCG 2017
Country/TerritoryCanada
CityOttawa
Period26/07/1728/07/17
Internet address

Fingerprint

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

Cite this