Canada Spends Logo

Explore our Budget 2026 analysis

Grant: Discovery Grants Program - Individual

Carleton University

$38,000.00

Design and Analysis of Algorithms for Problems in Computational Geometry

FY 2020-21

Summary
I study geometric problems within the framework of the design and analysis of algorithms. My long-term research objectives are to design, analyze and implement algorithms for problems that require spatial information and (a) are fundamental, (b) have practical significance, (c) are theoretically challenging and have the potential to raise new questions, (d) contribute to an understanding of a methodology or concept, and (e) lead to the development of generic techniques and tools that can be applied to other problems. This requires developing efficient algorithmic solutions, establishing combinatorial and geometric properties, designing appropriate data structures, providing correctness proofs and complexity bounds, and possibly implementations. In the short term, my research focus is in three interrelated areas: geometric graphs, geometric location analysis and geometric path problems. My work in geometric graphs is centred around establishing graph theoretic and geometric properties of the underlying spatial configuration that can lead to efficient algorithmic solutions. In geometric location analysis, we design algorithms to determine an optimal location for facilities. I plan to continue my research work on weighted shortest paths by exploring variants and applications in two and three-dimensional settings. As an illustration of my research directions consider the unit-disk graphs (UDG). UDG is a well-known class of geometric graphs that is often used to model the topology of ad hoc wireless communication networks. Each node, modelling an omni-directional antennae in the network, is viewed as a point in a plane. There is an edge between two nodes if the corresponding points are within a unit distance (signal strength outside this range is considered feeble). A signal can travel from one node to another if there are intermediate nodes between them so that a signal can hop from one node to other, each within a unit distance of its predecessor until it reaches the destination node. To check the connectivity between any pair of nodes, we can use a graph connectivity algorithm, and the time required is proportional to the size of the graph. Depending on the spatial configuration of the input nodes, a UDG can be anywhere from being very sparse to very dense. Therefore, the runtime of the configurations corresponding to the dense graphs is significantly higher than those corresponding to sparse graphs. By exploiting the geometric properties, we can design an algorithm to test the connectivity of UDG and ensure that its run-time is independent of the number of edges. Fundamental questions such as how to efficiently find a shortest hop path between a pair of query nodes, how to efficiently determine the diameter, and how to efficiently determine various graph parameters related to coverage, connectivity and interference questions in UDGs and the associated wireless networks remain unresolved.
Program
Discovery Grants Program - Individual
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data

As published

Application id
RGPIN-2016-06229
Name nom
Maheshwari, Anil
Department département
School of Computer Science
Organization id
23
Institution établissement
Carleton University
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2020
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
Installment
inst:5-5
Partie
1
Nb partie
5
Application title
Design and Analysis of Algorithms for Problems in Computational Geometry
Keyword
NSERC
Application summary
I study geometric problems within the framework of the design and analysis of algorithms. My long-term research objectives are to design, analyze and implement algorithms for problems that require spatial information and (a) are fundamental, (b) have practical significance, (c) are theoretically challenging and have the potential to raise new questions, (d) contribute to an understanding of a methodology or concept, and (e) lead to the development of generic techniques and tools that can be applied to other problems. This requires developing efficient algorithmic solutions, establishing combinatorial and geometric properties, designing appropriate data structures, providing correctness proofs and complexity bounds, and possibly implementations. In the short term, my research focus is in three interrelated areas: geometric graphs, geometric location analysis and geometric path problems. My work in geometric graphs is centred around establishing graph theoretic and geometric properties of the underlying spatial configuration that can lead to efficient algorithmic solutions. In geometric location analysis, we design algorithms to determine an optimal location for facilities. I plan to continue my research work on weighted shortest paths by exploring variants and applications in two and three-dimensional settings. As an illustration of my research directions consider the unit-disk graphs (UDG). UDG is a well-known class of geometric graphs that is often used to model the topology of ad hoc wireless communication networks. Each node, modelling an omni-directional antennae in the network, is viewed as a point in a plane. There is an edge between two nodes if the corresponding points are within a unit distance (signal strength outside this range is considered feeble). A signal can travel from one node to another if there are intermediate nodes between them so that a signal can hop from one node to other, each within a unit distance of its predecessor until it reaches the destination node. To check the connectivity between any pair of nodes, we can use a graph connectivity algorithm, and the time required is proportional to the size of the graph. Depending on the spatial configuration of the input nodes, a UDG can be anywhere from being very sparse to very dense. Therefore, the runtime of the configurations corresponding to the dense graphs is significantly higher than those corresponding to sparse graphs. By exploiting the geometric properties, we can design an algorithm to test the connectivity of UDG and ensure that its run-time is independent of the number of edges. Fundamental questions such as how to efficiently find a shortest hop path between a pair of query nodes, how to efficiently determine the diameter, and how to efficiently determine various graph parameters related to coverage, connectivity and interference questions in UDGs and the associated wireless networks remain unresolved.