Grant: Discovery Grants Program - Individual
University of Ottawa
$22,000.00
Strategic Route-Finding and Optimal Positioning in Geometric Environments
EF 2016-17
Résumé
My field of research is computational geometry, a field of computer science that focuses on solving problems with a strong geometric component. My long-term research objective is to uncover geometric properties in various scenarios to design and analyze efficient algorithms to solve fundamental problems in these different settings. For this research proposal, I want to focus on questions where we have to (1) find an optimal way to move in a geometric environment or (2) find an optimal placement for an object in a geometric environment.
To illustrate the first class of problems, suppose that you wake up from a nap in the middle of the woods. There is only one path but you do not remember which direction you came from. What should you do? In computational geometry, this problem is known as searching on a line. The goal is to minimize the total distance we have to walk before finding the exit, in the worst case. The optimal strategy is to walk 1 kilometre in one direction and get back. Then, walk twice the distance in the other direction and get back. And repeat until you find where you came from. This power-of-two strategy is used as a black box in other fields of computer science such as in networking for online routing algorithms, in distributed computing for deterministic rendez-vous problems and in robotics for path planning. Generally speaking, ``routing problem'' refers to an agent moving to find a target of known coordinates and ``rendez-vous problem'' consists of two or more agents trying to find each other. My short term research objectives in this area are inspired by these problems. For instance, one of my goals is to characterize the trade-offs between the constraints the agents need to deal with and the information that is available to the agents.
The second class of problems I focus on is related to finding an optimal location for an object in a given environment. For instance, where should we build a new hospital? What should be the trajectory for a new highway? People must have access to the facility as easily as possible, but we do not want to expropriate too many people in order to build the facility. My research work involves k-center problems where one looks for k points in the plane that minimize the distance to other points or to a frontier. I also work on optimal-enclosing problems where one wants to compute the optimal curve that encloses a set of points, with respect to a set of constraints. Another of my short term research objectives in this area is to find ways of modifying a network by adding/removing nodes or connections, in order to optimize different objective functions.
Several questions related to strategic route-finding and to optimal positioning remain open. As in many other fields, partial solutions to some of these problems naturally bring additional open questions on which I will work.
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
RGPIN-2016-05099
Name nom
DeCarufel, JeanLou
Department département
Electrical Engineering and Computer Science , School of - science informatique e
Organization id
28
Institution établissement
University of Ottawa
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2016
Competition year année de concours
2016
Award amount
22000
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
Partie
1
Nb partie
5
Application title
Strategic Route-Finding and Optimal Positioning in Geometric Environments
Keyword
NSERC
Application summary
My field of research is computational geometry, a field of computer science that focuses on solving problems with a strong geometric component. My long-term research objective is to uncover geometric properties in various scenarios to design and analyze efficient algorithms to solve fundamental problems in these different settings. For this research proposal, I want to focus on questions where we have to (1) find an optimal way to move in a geometric environment or (2) find an optimal placement for an object in a geometric environment.
To illustrate the first class of problems, suppose that you wake up from a nap in the middle of the woods. There is only one path but you do not remember which direction you came from. What should you do? In computational geometry, this problem is known as searching on a line. The goal is to minimize the total distance we have to walk before finding the exit, in the worst case. The optimal strategy is to walk 1 kilometre in one direction and get back. Then, walk twice the distance in the other direction and get back. And repeat until you find where you came from. This power-of-two strategy is used as a black box in other fields of computer science such as in networking for online routing algorithms, in distributed computing for deterministic rendez-vous problems and in robotics for path planning. Generally speaking, ``routing problem'' refers to an agent moving to find a target of known coordinates and ``rendez-vous problem'' consists of two or more agents trying to find each other. My short term research objectives in this area are inspired by these problems. For instance, one of my goals is to characterize the trade-offs between the constraints the agents need to deal with and the information that is available to the agents.
The second class of problems I focus on is related to finding an optimal location for an object in a given environment. For instance, where should we build a new hospital? What should be the trajectory for a new highway? People must have access to the facility as easily as possible, but we do not want to expropriate too many people in order to build the facility. My research work involves k-center problems where one looks for k points in the plane that minimize the distance to other points or to a frontier. I also work on optimal-enclosing problems where one wants to compute the optimal curve that encloses a set of points, with respect to a set of constraints. Another of my short term research objectives in this area is to find ways of modifying a network by adding/removing nodes or connections, in order to optimize different objective functions.
Several questions related to strategic route-finding and to optimal positioning remain open. As in many other fields, partial solutions to some of these problems naturally bring additional open questions on which I will work.