Personal tools
 

How to Walk Your Dog in the Mountains

Amir Nayyeri, U. of Illinois

What
  • Computer Science Seminar
  • Topology Seminar
When Tue, Feb 07, 2012
from 01:00 PM to 02:00 PM
Where TBA
Add event to calendar vCal
iCal

We describe a O(log n)-approximation algorithm for computing the
homotopic Frechet distance between two polygonal curves that lie on the boundary of a surface.

Prior to this work, algorithms were known only for curves on the Euclidean plane with polygonal obstacles.

A key technical ingredient in our analysis is an O(log n)-approximation algorithm for computing the minimum height of a homotopy between two curves. No algorithms were previously known for approximating this parameter. Surprisingly, it is not even known if computing either the homotopic Frechet distance, or the minimum height of a homotopy, is in NP.

Joint work with Sariel Har-Peled, Mohammad Salavatipour and Anastasios Sidiropoulos

« February 2018 »
February
SuMoTuWeThFrSa
123
45678910
11121314151617
18192021222324
25262728
Upcoming Events
Algebra Seminar
Tue, Feb 20, 2018
Complex and Arithmetic Dynamics of Monomial Maps Jan-Li Lin, Saint Louis, MO
AWM Meeting
Tue, Feb 20, 2018
Student Chapter of the Association of Women in Mathematics Organizational Meeting
Colloquium
Wed, Apr 18, 2018
Quantitative Topology? by Shmuel Weinberger, U Chicago
Previous events…
Upcoming events…