Seminar Calendar
for Special Graduate Geometry and Topology Seminar events the year of Monday, June 25, 2012.

     .
events for the
events containing  

(Requires a password.)
More information on this calendar program is available.
Questions regarding events or the calendar should be directed to Tori Corkery. 
       May 2012              June 2012              July 2012      
 Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa   Su Mo Tu We Th Fr Sa
        1  2  3  4  5                   1  2    1  2  3  4  5  6  7
  6  7  8  9 10 11 12    3  4  5  6  7  8  9    8  9 10 11 12 13 14
 13 14 15 16 17 18 19   10 11 12 13 14 15 16   15 16 17 18 19 20 21
 20 21 22 23 24 25 26   17 18 19 20 21 22 23   22 23 24 25 26 27 28
 27 28 29 30 31         24 25 26 27 28 29 30   29 30 31

Thursday, May 3, 2012

Special Graduate Geometry and Topology Seminar
12:00 pm   in 241 Altgeld Hall,  Thursday, May 3, 2012
 Del 
 Edit 
 Copy 
Submitted by lukyane2.
Amir Nayyeri (UIUC Computer Science)
How to Walk Your Dog in the Mountains
Abstract: 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 where known only for curves on the Euclidean plane with polygonal obstacles. A key technical ingredient in our analysis is a $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