Personal tools

How to Walk Your Dog in the Mountains

Amir Nayyeri, U. of Illinois

  • 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

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 »
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
Wed, Apr 18, 2018
Quantitative Topology? by Shmuel Weinberger, U Chicago
Previous events…
Upcoming events…