Campus Event Calendar
Event Entry
What and Who
Improving Computational Upper and Conditional Lower Bounds of Fréchet Distance on Practical Input Curves (Bachelor thesis)
Nico Gründel
Fachrichtung Informatik - Saarbrücken
AG1 Mittagsseminar (own work)
AG 1
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 17 December 2019
13:00
30 Minutes
E1 4
024
Saarbrücken
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
Karl Bringmann
--email hidden
passcode not visible
logged in users only
Karl Bringmann, 11/30/2019 13:19 -- Created document.