Max-Planck-Institut für Informatik
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:Improving Computational Upper and Conditional Lower Bounds of Fréchet Distance on Practical Input Curves (Bachelor thesis)
Speaker:Nico Gründel
coming from:Fachrichtung Informatik - Saarbrücken
Speakers Bio:
Event Type:AG1 Mittagsseminar (own work)
Visibility:D1
We use this to send out email in the morning.
Level:AG Audience
Language:English
Date, Time and Location
Date:Tuesday, 17 December 2019
Time:13:00
Duration:30 Minutes
Location:Saarbrücken
Building:E1 4
Room:024
Abstract
The Fréchet Distance is a measurement of similarity between polygonal curves, which has applications in many different areas of computer science. Many of these applications, however, encompass only a narrow set of inputs. For this purpose, there have been efforts in finding faster algorithms for certain curve types, such as κ-bounded and κ-straight curves. There are currently no known conditional lower bounds for the Fréchet Distance on both κ-straight and κ-bounded curves matching the fastest known algorithms. In this work we show that the fastest algorithm for κ-bounded curves is in fact faster than thought, and propose a matching lower bound for both κ-straight and κ-bounded curves.
Contact
Name(s):Karl Bringmann
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Note:
Attachments, File(s):
  • Karl Bringmann, 11/30/2019 01:19 PM -- Created document.