Event Details
Turning Sketched Paths into Shortest Paths
Presenter: Dr. Anna Lubiw - Professor, Department of Computer Science, University of Waterloo
Supervisor: Dr. F. Ruskey, Professor, Department of Computer Science
Date: Wed, June 19, 2002
Time: 15:00:00 - 16:00:00
Place: Human Social Development Building, (HSD) Room # A240
ABSTRACT
ABSTRACT:
Given n point obstacles in the plane and some ``sketches'' of disjoint paths that wind amongst the points, we give an efficient algorithm to turn the sketched paths into shortest paths that still wind amongst the points in the same way; i.e., that are homotopic to the original paths.
This problem of computing shortest homotopic paths has application to graph drawing, wire routing in circuit board design, and motion planning. The talk will include background on geometric shortest path problems.
This is joint work with Alon Efrat and Stephen Kobourov.