Grant: Discovery Grants Program - Individual
University of Waterloo
$43,000.00
Algorithms in computational geometry and graph drawing
FY 2012-13
Summary
My research is in design and analysis of algorithms -- specifically in the areas of computational geometry and graph algorithms. Graph representations are ubiquitous in computer science, engineering and the sciences -- a few examples are: road/electical/internet networks in engineering, and molecular structures in chemistry and biology. Geometry, sometimes intrinsic, and sometimes imposed, is often a valuable part of a graph representation. A big part of my work is about devising algorithms to find, manipulate and utilize such geometric representations of graphs. Specifically, I propose working on algorithms to represent two graphs that share some vertices and edges, with the constraint that the shared part be represented consistently.
In computational geometry, a recent area of concentration is the study of algorithms to change geometric configurations over time. ""Morphing'' is the popular term for some special cases of this, though more broadly, this area includes motion planning problems, folding problems, and problems of interpolating between 2-dimensional slices of a 3-dimensional object -- with applications to robotics, manufacturing, and medical imaging, respectively. I propose working on algorithms to morph between two representations of the same graph while preserving some geometric structure such as planarity, angles or lengths.
In both the geometric setting and in graphs, shortest paths are a continued source of interesting and practical problems. I will pursue on-going work on finding shortest paths on terrains, such as the earth's surface, while observing height constraints, such as going downhill but not too steeply. I will also work on shortest paths in graphs for the situation where some subpaths are forbidden, but the forbidden set is not known in advance. This has applications in optical network routing and vehicle dispatching.
Program
Discovery Grants Program - Individual
Recipient
Location
Ontario, Canada
Recipient Type
Academia
Type
Grant
Source
NSERC's Awards Data
As published
Application id
36704-2010
Name nom
Lubiw, Anna
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2012
Competition year année de concours
2010
Award amount
43000
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
9999
Area of application group en
Not available
Area of application group fr
Non disponible
Area of application en
Not available
Area of application fr
Non disponible
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
Algorithms in computational geometry and graph drawing
Keyword
NSERC
Application summary
My research is in design and analysis of algorithms -- specifically in the areas of computational geometry and graph algorithms. Graph representations are ubiquitous in computer science, engineering and the sciences -- a few examples are: road/electical/internet networks in engineering, and molecular structures in chemistry and biology. Geometry, sometimes intrinsic, and sometimes imposed, is often a valuable part of a graph representation. A big part of my work is about devising algorithms to find, manipulate and utilize such geometric representations of graphs. Specifically, I propose working on algorithms to represent two graphs that share some vertices and edges, with the constraint that the shared part be represented consistently.
In computational geometry, a recent area of concentration is the study of algorithms to change geometric configurations over time. ""Morphing'' is the popular term for some special cases of this, though more broadly, this area includes motion planning problems, folding problems, and problems of interpolating between 2-dimensional slices of a 3-dimensional object -- with applications to robotics, manufacturing, and medical imaging, respectively. I propose working on algorithms to morph between two representations of the same graph while preserving some geometric structure such as planarity, angles or lengths.
In both the geometric setting and in graphs, shortest paths are a continued source of interesting and practical problems. I will pursue on-going work on finding shortest paths on terrains, such as the earth's surface, while observing height constraints, such as going downhill but not too steeply. I will also work on shortest paths in graphs for the situation where some subpaths are forbidden, but the forbidden set is not known in advance. This has applications in optical network routing and vehicle dispatching.