Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Carleton University

$38,000.00

Dynamic Shortest Path Algorithms and their Applications

EF 2017-18

Résumé
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.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2016-06253
Name nom
Sack, JËrgRüdiger
Department département
Computer Science, School of - Computer Science, School of
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2017
Competition year année de concours
2016
Award amount
38000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
Discovery grants programs
Group fr
Programmes de subventions à la découverte
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
2
Nb partie
5
Application title
Dynamic Shortest Path Algorithms and their Applications
Keyword
NSERC
Application summary
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.