Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

University of Saskatchewan

$19,000.00

Algorithmic approaches to hard geometric and graph theoretic problems

EF 2013-14

Résumé
Constructing and manipulating a computational model is central in many computer science applications. Unfortunately, often the problems that naturally arise turn out to be hard, in the sense that the best known algorithms cannot find exact solutions in a reasonable amount of time. Computational models involving graphs are pervasive in applications, and where physical objects are modeled, geometric models are important. The objective of this research program is to develop effective algorithmic approaches to some natural hard geometric and graph theoretic problems. The approaches will include the development of algorithms that yield approximate solutions as well as algorithms that yield exact solutions but only to restricted instances of the problems.The overall approach is to focus on the interplay between the areas of algorithmic graph theory and computational geometry. We will seek to exploit the natural relationships that exist among the problems, concepts and techniques of the two areas.In this research we focus on the following areas: polygon decomposition, triangulation, proximity problems and intersection graphs. In each of these areas there are many hard problems that arise in applications and in each there exists interplay between computational geometry and graph theory. In polygon decomposition, the goal is to represent a polygon as the union of a small number of simple components which are easier to subsequently process. Likewise a triangulation is used to represent a complex area as the union of triangles.This can be done in many different ways and sometimes the best way may be expensive to compute. Proximity problems involve computations that depend upon the distances between objects. Intersection graphs can arise from modeling a geometric problem with graphs.
Programme
Discovery Grants Program - Individual
Emplacement
Saskatchewan, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
259-2009
Name nom
Keil, Mark
Department département
Computer Science
Organization id
16
Institution établissement
University of Saskatchewan
Province en
Saskatchewan
Province fr
Saskatchewan
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2013
Competition year année de concours
2009
Award amount
19000
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
331
Committee name en
Computing and Information Sciences - B
Committee name fr
Informatique - B
Area of application code
802
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
Information systems and technology
Area of application fr
Systèmes d'information et technologie de l'information
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
Algorithmic approaches to hard geometric and graph theoretic problems
Keyword
NSERC
Application summary
Constructing and manipulating a computational model is central in many computer science applications. Unfortunately, often the problems that naturally arise turn out to be hard, in the sense that the best known algorithms cannot find exact solutions in a reasonable amount of time. Computational models involving graphs are pervasive in applications, and where physical objects are modeled, geometric models are important. The objective of this research program is to develop effective algorithmic approaches to some natural hard geometric and graph theoretic problems. The approaches will include the development of algorithms that yield approximate solutions as well as algorithms that yield exact solutions but only to restricted instances of the problems.The overall approach is to focus on the interplay between the areas of algorithmic graph theory and computational geometry. We will seek to exploit the natural relationships that exist among the problems, concepts and techniques of the two areas.In this research we focus on the following areas: polygon decomposition, triangulation, proximity problems and intersection graphs. In each of these areas there are many hard problems that arise in applications and in each there exists interplay between computational geometry and graph theory. In polygon decomposition, the goal is to represent a polygon as the union of a small number of simple components which are easier to subsequently process. Likewise a triangulation is used to represent a complex area as the union of triangles.This can be done in many different ways and sometimes the best way may be expensive to compute. Proximity problems involve computations that depend upon the distances between objects. Intersection graphs can arise from modeling a geometric problem with graphs.