Fast Fréchet queries

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review


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+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é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.
Originele taal-2Engels
TitelAlgorithms and Computation (22nd International Symposium, ISAAC 2011, Yokohama, Japan, December 5-8, 2011. Proceedings)
RedacteurenT. Asano, S. Nakano, Y. Okamoto, O. Watanabe
Plaats van productieBerlin
ISBN van geprinte versie978-3-642-25590-8
StatusGepubliceerd - 2011

Publicatie series

NaamLecture Notes in Computer Science
ISSN van geprinte versie0302-9743


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

Citeer dit