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
Computer Science Seminar
Mon, Feb 19, 2018
Software Systems Engineering with Evolutionary Algorithms Kate Holdener
Computer Science Seminar
Wed, Feb 21, 2018
Secure Software Development using Agile Approach: Issues and Potential Solutions Imran Ghani, Monash University Malaysia
Previous events…
Upcoming events…