Research:
People:
Prospective Students:
|
|
Algorithms and Complexity Seminar
|
| |
|
| Date: |
Thursday, August 2, 2007
|
| Time: |
1:30 PM
|
| Place: |
DC1304
|
| |
|
| |
|
| Title: |
Approximation Algorithms for Shortest Descending Paths
|
| Speaker: |
Mustaq Ahmed, School of Computer Science, University of Waterloo
|
|
|
Abstract: |
| |
|
A path from s to t on a polyhedral terrain is descending if the height
of a point p never increases while we move p along the path from s to
t. No efficient algorithm is known to find a shortest descending path
(SDP) from s to t in a polyhedral terrain. In this talk we will prove
some properties of an SDP, and give an O( n^{3.5} log(1/epsilon) )-time
algorithm to compute a (1+epsilon)-approximate SDP through a
given sequence of faces. We will also present a new approach of
discretizing the terrain with Steiner points, which makes it possible
to preprocess the terrain in O( n^2 X/epsilon log(n X/epsilon) ) time
so that we can determine a (1+epsilon)-approximate SDP from s to any
point v in O(n) time if v is a vertex of the terrain, and in
O(n X/epsilon)$ time otherwise. Here n is the size of the terrain, and
X is a parameter of the geometry of the terrain.
|
|
|
