Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Carleton University

$29,000.00

Design, analysis and implementation of geometric and graph algorithms

EF 2014-15

Résumé
We will design, analyze and implement algorithms for problems arising in computational geometry and graph algorithms. Wherever possible, we will show upper and lower bounds in terms of computing resources used (time, space, processors, I/Os), provide the proof of correctness, and show the optimality or approximation bounds. The problems that we will study will likely be an abstraction, or a simplification or a generalization of problems that occur in practice. In computational geometry, we will primarily focus on shortest path problems, spanners, constrained geometrical queries and data structures. In graph algorithms, the focus will be on planar separators, problems that are at the interface of geometry and graph theory, understanding graph theoretic properties of geometric spanners, designing algorithms for problems based on geometric graphs, and especially studying graph problems where the underlying problem domain is geometric. Over the next five years, we want to expand our existing work on geometric shortest path problems on polyhedral domains by designing algorithms for three-dimensional weighted shortest path problems, generalizing the weight requirements from fixed to continuous, finding a suitable triangulation which leads to the given shortest path distances, and finding practically-relevant algorithms. We will expand our research work on geometric spanners by designing spanners for constrained domains that satisfy useful graph-theoretic properties that will likely lead to faster algorithms. We will further expand our work on `localized geometric queries' (e.g., find the largest empty circle containing a query point). The speed-constrained versions of the Frechet distance (which is a very commonly used similarity measure between two curves) based problems and their variants will be further explored. Some of our algorithms and techniques may find applications in designing economical and efficient networks, finding short, time-optimum, paths in geographical domains, and ways to represent geometric data succinctly to answer queries efficiently.
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
195732-2011
Name nom
Maheshwari, Anil
Department département
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
2014
Competition year année de concours
2011
Award amount
29000
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
801
Area of application group en
Information and communication services
Area of application group fr
Services d'information et de télécommunications
Area of application en
Computer software
Area of application fr
Logiciel
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
4
Nb partie
5
Application title
Design, analysis and implementation of geometric and graph algorithms
Keyword
NSERC
Application summary
We will design, analyze and implement algorithms for problems arising in computational geometry and graph algorithms. Wherever possible, we will show upper and lower bounds in terms of computing resources used (time, space, processors, I/Os), provide the proof of correctness, and show the optimality or approximation bounds. The problems that we will study will likely be an abstraction, or a simplification or a generalization of problems that occur in practice. In computational geometry, we will primarily focus on shortest path problems, spanners, constrained geometrical queries and data structures. In graph algorithms, the focus will be on planar separators, problems that are at the interface of geometry and graph theory, understanding graph theoretic properties of geometric spanners, designing algorithms for problems based on geometric graphs, and especially studying graph problems where the underlying problem domain is geometric. Over the next five years, we want to expand our existing work on geometric shortest path problems on polyhedral domains by designing algorithms for three-dimensional weighted shortest path problems, generalizing the weight requirements from fixed to continuous, finding a suitable triangulation which leads to the given shortest path distances, and finding practically-relevant algorithms. We will expand our research work on geometric spanners by designing spanners for constrained domains that satisfy useful graph-theoretic properties that will likely lead to faster algorithms. We will further expand our work on `localized geometric queries' (e.g., find the largest empty circle containing a query point). The speed-constrained versions of the Frechet distance (which is a very commonly used similarity measure between two curves) based problems and their variants will be further explored. Some of our algorithms and techniques may find applications in designing economical and efficient networks, finding short, time-optimum, paths in geographical domains, and ways to represent geometric data succinctly to answer queries efficiently.