Walking Your Dog in the Woods in Polynomial Time

Speaker: Shripad Thite, CalTech
Host: Prof. David KempeAbstract:
The Frechet distance between two curves in the plane is the minimum length of a leash that allows a dog and its owner to walk along their respective curves, from one end to the other, without backtracking. We propose a natural extension of Frechet distance to more general metric spaces, which requires the leash itself to move continuously over time. For example, for curves in the punctured plane, the leash cannot pass through or jump over obstacles (``trees''). Thus, we introduce the homotopic Frechet distance between two curves embedded in a general metric space. We describe a polynomial-time algorithm to compute the homotopic Frechet distance between two given polygonal curves in the plane minus a given set of polygonal obstacles. Our algorithm produces a walk that minimizes the maximum leash length.This is joint work with Erin Wolf Chambers, Eric Colin de Verdiere, Jeff Erickson, Sylvain Lazard, and Francis Lazarus, which appeared at SoCG'08 in June and was invited to a CGTA special issue.Biography:
Shripad is a postdoctoral fellow in the Center for the Mathematics of Information (CMI) at Caltech. His research is in algorithms, specifically in computational geometry and topology. He designs algorithms for fundamental problems in computational geometry as well as algorithms for geometric problems in applied areas, including scientific computing, graphics and visualization, wireless networking, robotics, and even computational economics. Shripad earned his Ph.D. in Computer Science from the University of Illinois at Urbana-Champaign with Jeff Erickson, and then spent two years at the Technische Universiteit Eindhoven in the Netherlands working with Mark de Berg, before joining Caltech last year.

Location: Seaver Science Library (SSL) - 150

Audiences: Everyone Is Invited

Contact: CS Colloquia