Seminar Calendar
for Special Graduate Geometry and Topology Seminar events the year of Saturday, August 18, 2012.

.
events for the
events containing

Questions regarding events or the calendar should be directed to Tori Corkery.
      July 2012             August 2012           September 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  6  7             1  2  3  4                      1
8  9 10 11 12 13 14    5  6  7  8  9 10 11    2  3  4  5  6  7  8
15 16 17 18 19 20 21   12 13 14 15 16 17 18    9 10 11 12 13 14 15
22 23 24 25 26 27 28   19 20 21 22 23 24 25   16 17 18 19 20 21 22
29 30 31               26 27 28 29 30 31      23 24 25 26 27 28 29
30


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 MountainsAbstract: 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