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

« November 2017 »
November
SuMoTuWeThFrSa
1234
567891011
12131415161718
19202122232425
2627282930