Fast Fréchet queries

M.T. Berg, de, A.F. Cook IV, J. Gudmundsson

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

16 Citaten (Scopus)
2 Downloads (Pure)


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é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échet distance is at most e, but this count may also include subpaths whose Fréchet distance is up to (2+3v2)e. For any parameter n=s=n2, our data structure can be tuned such that it uses O(s polylog n) storage and has O((n/vs) polylog n) query time.
Originele taal-2Engels
Pagina's (van-tot)747-755
TijdschriftComputational Geometry
Nummer van het tijdschrift6
StatusGepubliceerd - 2013

Vingerafdruk Duik in de onderzoeksthema's van 'Fast Fréchet queries'. Samen vormen ze een unieke vingerafdruk.

Citeer dit