Grant: Discovery Grants Program - Individual
Carleton University
$28,000.00
Design, analysis and implementation of discrete algorithms for graph and computational geometry problems
FY 2008-09
Summary
The proposed research is in the field of design, analysis and implementation of algorithms, a subfield within theoretical computer science. We focus on problems arising in computational geometry and graph theory. The problems include (a) Geometric path problems - how to find a path between two points in a geometric domain (surface, planar region, three dimensional space amidst obstacles) under various constraints (shortest, monotone descending, minimizing the number of links, multiple criteria) (b) Graph separators - computing vertex/edge separators of planar (or planar like) graphs (c) Visibility optimization problems (with applications in radiation therapy) - need to see a polyhedra (tumor), avoiding/minimizing a set a polyhedra (healthy organs), from a minimum set of locations (possible position of laser guns placed outside the body) (d) Developing generic external memory algorithmic techniques for solving graph and geometric problems (e) Developing algorithmic technqiues for solving problems in variety of computational models - external memory model, parallel computing model, priced information model, streaming and models with very limited extra space (f) Approximation algorithms based on discretization - we have proposed discretization based schemes to solve geometric path problems. Most often spatial problems arising in practical settings are solved by heuristics using some form of discretization. We propose to study these problems, in light of our results, and hope to provide approximation algorithms with provable bounds in terms of their accuracy and complexity (g) Analyzing complexity of geometric algorithms using geometric parameters - traditionally the complexity of geometric algorithms is analyzed with respect to input parameters (number of segments, vertices, faces, etc.), but often in practice, the run-time is very sensitive to geometric parameters - angle, distance, fatness. So the design of the algorithm needs to take these parameters into account; this came up in our work on shortest paths. We propose to expand the design and analysis of geometric algorithms to include geometric parameters (h) Finding ways to make geometrical concepts presentable on the web in an interactive manner.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
195732-2006
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
2008
Competition year année de concours
2006
Award amount
28000
Program id
RGPIN
Program nane 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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
1205
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Mathematical sciences
Area of application fr
Sciences mathématiques
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
3
Nb partie
5
Application title
Design, analysis and implementation of discrete algorithms for graph and computational geometry problems
Keyword
NA
Application summary
The proposed research is in the field of design, analysis and implementation of algorithms, a subfield within theoretical computer science. We focus on problems arising in computational geometry and graph theory. The problems include (a) Geometric path problems - how to find a path between two points in a geometric domain (surface, planar region, three dimensional space amidst obstacles) under various constraints (shortest, monotone descending, minimizing the number of links, multiple criteria) (b) Graph separators - computing vertex/edge separators of planar (or planar like) graphs (c) Visibility optimization problems (with applications in radiation therapy) - need to see a polyhedra (tumor), avoiding/minimizing a set a polyhedra (healthy organs), from a minimum set of locations (possible position of laser guns placed outside the body) (d) Developing generic external memory algorithmic techniques for solving graph and geometric problems (e) Developing algorithmic technqiues for solving problems in variety of computational models - external memory model, parallel computing model, priced information model, streaming and models with very limited extra space (f) Approximation algorithms based on discretization - we have proposed discretization based schemes to solve geometric path problems. Most often spatial problems arising in practical settings are solved by heuristics using some form of discretization. We propose to study these problems, in light of our results, and hope to provide approximation algorithms with provable bounds in terms of their accuracy and complexity (g) Analyzing complexity of geometric algorithms using geometric parameters - traditionally the complexity of geometric algorithms is analyzed with respect to input parameters (number of segments, vertices, faces, etc.), but often in practice, the run-time is very sensitive to geometric parameters - angle, distance, fatness. So the design of the algorithm needs to take these parameters into account; this came up in our work on shortest paths. We propose to expand the design and analysis of geometric algorithms to include geometric parameters (h) Finding ways to make geometrical concepts presentable on the web in an interactive manner.