Grant: Discovery Grants Program - Individual
University of Waterloo
$20,000.00
Algorithms for geometric reconstruction problems
EF 2014-15
Résumé
Anyone who has ever played a pen-and-paper puzzle (such as Sudoku, Kakuro, Nonogram or Bridges) has solved a reconstruction problem: given some partial information about an object, reconstruct the object from it. I propose to study such reconstruction problems, which are motivated not only by puzzles, but more importantly by many medical and industrial applications. My approach is from a theoretical computer science point of view. Thus, the main question is: ""Can this reconstruction problem be solved by a computer in reasonably short time?"" If yes, then the goal is to find the fastest possible algorithm to do so. If no, then heuristics are required, and my goal is to develop heuristics that performs provably well, at least in some special cases.My focus is on reconstruction problems that have a geometric flavour, such as reconstructing a 0/1-matrix given information about its thickness in various projections (the mathematical formulation of Nonogram), or reconstructing a polyhedron given information about its graph and some of the angles. Most of these problems are known to be NP-hard, i.e., likely have no efficient algorithms. My approach is to focus on special cases, and to develop algorithms that can solve these special cases. I then try to generalize these algorithms such that they can solve all cases, at the cost of a (controlled) increase in time complexity, depending on some parameter of the problem.
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
227718-2010
Name nom
Biedl, Therese
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
2014
Competition year année de concours
2010
Award amount
20000
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
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
5
Nb partie
5
Application title
Algorithms for geometric reconstruction problems
Keyword
NSERC
Application summary
Anyone who has ever played a pen-and-paper puzzle (such as Sudoku, Kakuro, Nonogram or Bridges) has solved a reconstruction problem: given some partial information about an object, reconstruct the object from it. I propose to study such reconstruction problems, which are motivated not only by puzzles, but more importantly by many medical and industrial applications. My approach is from a theoretical computer science point of view. Thus, the main question is: ""Can this reconstruction problem be solved by a computer in reasonably short time?"" If yes, then the goal is to find the fastest possible algorithm to do so. If no, then heuristics are required, and my goal is to develop heuristics that performs provably well, at least in some special cases.My focus is on reconstruction problems that have a geometric flavour, such as reconstructing a 0/1-matrix given information about its thickness in various projections (the mathematical formulation of Nonogram), or reconstructing a polyhedron given information about its graph and some of the angles. Most of these problems are known to be NP-hard, i.e., likely have no efficient algorithms. My approach is to focus on special cases, and to develop algorithms that can solve these special cases. I then try to generalize these algorithms such that they can solve all cases, at the cost of a (controlled) increase in time complexity, depending on some parameter of the problem.