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

time.

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

### Like this:

Like Loading...

*Related*

## Discussion

## No comments yet.