Dynamic Shortest Path Algorithms and their Applications

点击翻译按钮获取中文摘要

In many applications arising e.g., in Robotics, GIS, Navigation, Social Networks, and Sensor Networks, environments are dynamic. Objects/entities may move, disappear, appear and even change shape. Traditional shortest path algorithms, designed for static environments, would either not be applicable or require frequent recomputations and thus become inefficient.****Most activity for dynamic shortest path problems has been in the area of graph (or hyper-graph). These instances allow for graph edges to be inserted and/or deleted and/or weights to be changed. Fully dynamic algorithms allow edges to be both inserted and deleted; partially dynamic algorithms allow for either insertions or deletions, but not both. Results exist for both fully and partially dynamic algorithms.****Building on, and motivated by, previous work, we are interested in dynamic shortest path algorithms for solving geometric problems. For example, objects (obstacles for the shortest path computation) may only exist for a fixed time interval [Ts, Te], i.e., the object appears at time Ts and disappears at time Te. Objects may change shape over time (say grow continuously from a point to larger and larger circles - such problems arise when one wants to model uncertainties). Another interesting class of dynamic shortest paths problems arises in time-dependent graphs or networks, where the costs of edges (that is, edge travel times) vary as a function of time, and as a result the shortest path between two nodes s and d can change over time. ****We have already studied similarities of polygonal curves measured via the frequently used Fréchet Distance. Similarity problems between polygonal curves arise e.g. in Computer Graphics, Pattern Recognition, Clustering, GIS and structural biology, sports scene analysis, human movement, surveillance, and animal behavior. We discovered and/or improved upon some exciting and natural optimization problems involving the Fréchet Distance. The solution often involved solving particular shortest path problems. To solve several new optimization and parameterization problems using the Fréchet Distance and its variants, we will encounter geometric dynamic shortest path problems. Solutions to these are also of independent interest and will enable us to obtain also solutions to these Fréchet Distance problems. **