you're reading...

Fast Fréchet Queries – Joachim Gudmundsson

Hi all,

This Friday’s SACT seminar is again at the usual time and place of 11am in the boardroom.

Title: Fast Fré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
Frechet distance to a given query segment Q is at most some threshold
value \eps. We present a data structure that solves an approximate
version of this problem: it counts all subpaths whose Frechet distance
is at most \eps, but this count may also include subpaths whose
Frechet distance is up to (2+3\sqrt{2})\eps. 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}) polylog n) query
time. For the special case where we wish to count all subpaths
whose Frechet distance to Q is at most \eps * length(Q), we present a
structure with O(n polylog n) storage and O(polylog n) query

This is joint work with Mark de Berg and Atlas F. Cook IV



No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Enter your email address to subscribe to receive notifications of new announcements by email.

Join 61 other followers

%d bloggers like this: