The flow path problem

Carsten Grimm

We are given a point robot in the plane, a triangulation of a polygon with holes, speed bounds for the robot within each triangular face and a face-wise constant flow disturbing the robot's movement. The question of how to navigate the point robot from its starting point to a destination within the shortest period of time has been introduced as the "flow path problem" by Reif and Sun in 2004. However, only a theoretical decision algorithm for the general case and an approximation schema for a special case based on a discretization technique are known. This talk will summarize these results and describe the various difficulties that occur when said discretization approach is applied on the general case.