@inproceedings{cfa28219e6c3434285ad9d44dd4aa67b,

title = "Fast Fr{\'e}chet queries",

abstract = "Inspired by video analysis of team sports, we study the following problem. Let P be a polygonal path in the plane with n vertices. We want to preprocess P into a data structure that can quickly count the number of inclusion-minimal subpaths of P whose Fr{\'e}chet Distance to a given query segment Q is at most some threshold value e. We present a data structure that solves an approximate version of this problem: it counts all subpaths whose Fr{\'e}chet Distance is at most e, but this count may also include subpaths whose Fr{\'e}chet Distance is up to (2+3 \sqrt 2) . For any parameter n¿=¿s¿=¿n 2, our data structure can be tuned such that it uses O(s polylog n) storage and has O((n/\sqrt) polylog n) query time. For the special case where we wish to count all subpaths whose Fr{\'e}chet Distance to Q is at most e·length(Q), we present a structure with O(n polylog n) storage and O(polylog n) query time.",

author = "{Berg, de}, M.T. and {Cook IV}, A.F. and J. Gudmundsson",

year = "2011",

doi = "10.1007/978-3-642-25591-5_26",

language = "English",

isbn = "978-3-642-25590-8",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "240--249",

editor = "T. Asano and S. Nakano and Y. Okamoto and O. Watanabe",

booktitle = "Algorithms and Computation (22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings)",

address = "Germany",

}