MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

Approximate Near-Neighbor Problem for Curves using Discrete Fréchet Distance under Translation and Rotation (Master thesis)

Zahra Parsaeian
Max-Planck-Institut für Informatik - D1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Tuesday, 29 November 2022
13:00
30 Minutes
E1 4
024
Saarbrücken

Abstract

Polygonal curves have an important role in pattern matching, protein structure-structure alignment, and computer graphics. Hence, having a measure to compare the similarity of polygonal curves is essential.


There are several studied similarity measures; among them, Fréchet distance is an essential measure. Consider a man and his dog connected by a leash and walking on two curves at any speed. The Fréchet distance is the minimum leash length needed for walking along the curves.

In this thesis, we work with the discrete version of Fréchet distance where curves are not continuous; instead of the man and the dog walking continuously, they jump over vertices of discrete curves. If we can implement some transformation on curves, we might be able to improve the comparison of curves.

In this thesis, we study the following problem: Given a set of curves $\mathcal{C}$ and a query curve $Q$, if there is a curve with discrete Fréchet distance $r$ (under \emph{translation} or \emph{rotation}) from the queue in set $\mathcal{C}$, we will return a curve $C^{\star}$ with distance $(1 + \epsilon)r$ from $Q$.

Contact

Roohani Sharma
+49 681 9325 1116

Virtual Meeting Details

Zoom
527 278 8807
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

If you wish to attend the talk online but do not have the password, contact Roohani Sharma at rsharma@mpi-inf.mpg.de.

Roohani Sharma, 11/15/2022 16:46
Roohani Sharma, 11/15/2022 16:40 -- Created document.