Advertisement
Published in:
2011 | OriginalPaper | Chapter
Fast Fréchet Queries
Authors : Mark de Berg, Atlas F. Cook IV, Joachim Gudmundsson
Published in: Algorithms and Computation
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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
ε
. We present a data structure that solves an approximate version of this problem: it counts all subpaths whose Fréchet Distance is at most
ε
, but this count may also include subpaths whose Fréchet Distance is up to
$(2+3\sqrt{2})\varepsilon $
. 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{s}){\rm polylog} n)$
query time. For the special case where we wish to count all subpaths whose Fréchet Distance to
Q
is at most
ε
·
length
(
Q
), we present a structure with
O
(
n
polylog
n
) storage and
O
(polylog
n
) query time.