06.07.2015

Informatik-Kolloquium

Im Sommersemester 2015 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Montag, 6. Juli 2015, 16.15 Uhr, Turing-Hörsaal

Prof. Dr. Rajasekhar Inkulu, IIT Guwahati, Indien

Finding an Approximate Shortest Path amid Weighted Regions

Given a triangulated region R that consists of n triangles each associated with a positive weight, two points s and t in R, and 0 < epsilon < 1, we want to find a path between s and t whose cost is at most (1+epsilon) times the cost of an optimal path between s and t. The cost of a polygonal path in R is the weighted sum of the line segments that it comprises of. A shortest (or, an optimal) path between s and t is a path that has the least cost among all the paths between s and t.

The talk starts with presenting various properties of geodesic shortest paths in weighted regions from Mitchell and Papadimitriou ’(1991), and details their polynomial-time algorithm. Their algorithm progresses the intervals of optimality (a variant of a discrete Dijkstra wavefront) in the geometric domain from s to t. Then, we give an overview over practical but pseudo-polynomial-time algorithms; these algorithms primarily reduce the geometric least cost-path finding problem to a graph-theoretic single-source shortest path problem (rooted at s). Finally, we present an own recent result: the first polynomial-time algorithm since the result of Mitchell and Papadimitriou. Our algorithm initiates a discrete Dijkstra wavefront from s and expands it over R. We decrease the running time by a cubic factor while optimizing the number of events points involved.