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

« December 2017 »
December
SuMoTuWeThFrSa
12
3456789
10111213141516
17181920212223
24252627282930
31