Canada Spends Logo

Explorez notre analyse du budget 2026

Grant: Discovery Grants Program - Individual

Simon Fraser University

$24,000.00

Attraction, Repulsion, and Facility Location

EF 2022-23

Résumé
My main objective is to investigate algorithms and basic mathematics for attraction and repulsion, with a focus on facility location problems. Attraction (also known as beacon attraction) was recently introduced by Biro with substantial other work from Kostitsnya and Kouhestani. In this model, an activated beacon will cause all particles to move directly towards it, or to slide along a wall if that brings it closer to the beacon. (Here the particles model robots, or messages in a network.) Bose and I introduced a corresponding notion of repulsion. The attraction relation includes visibility, and visibility has a rich theory with many algorithms and combinatorial results. Finding counterparts of these results for attraction is a wide open and exciting new direction, but it also encounters difficulties, often to do with the fact that attraction is not a symmetric relation, whereas visibility is. It is thus ripe for serious study. The study of repulsion encounters even more difficulties than attraction. Visibility and attraction are relations amongst two points (point a can see point b, or a can attract b), and thus their problem formulations and some methodology regarding them are derived from graph theory. Repulsion is a relation amongst three points: point a can repulse point b to some third point c. Therefore even the usual problem formulations may not apply; this makes the area of repulsion particularly interesting. I intend to employ classic computational geometry methodology in my investigation of these topics. This involves studying the basic geometry and combinatorial properties of the relations and designing algorithms that use these properties to answer questions about particular situations. For example, one particular problem that I will investigate is how to preprocess a polygonal domain D so that one may efficiently answer questions of the form: given an attraction beacon b and a point p in D, where does the point p move to if we activate the beacon b? Here, we also get a meaningful question if we replace the attraction beacon with a repulsion actuator. The intended research is a mix of basic research (studying the geometric and combinatorial properties of these relations) and applied research (designing algorithms to answer relevant questions). There are at least three possible application areas of this study. The first is in message routing in sensor networks; the idea of greedy geographical routing is a discretization of attraction. The second application would be in robotics, to understand the behaviour of a robot operating to move towards (attraction) or away from (repulsion) a homing beacon. A third application might be in modelling crowd behaviour, where there may be stimuli of attraction (a place where everyone wants to be) and repulsion (a place that everyone wants to get away from, such as a fire).
Programme
Discovery Grants Program - Individual
Emplacement
British Columbia, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data

Tel que publié

Application id
RGPIN-2020-05404
Name nom
Shermer, Thomas
Department département
Computing Science, School of - Computing Science, School of
Organization id
5
Institution établissement
Simon Fraser University
Province en
British Columbia
Province fr
Colombie-Britannique
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2022
Competition year année de concours
2020
Award amount
24000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
803
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
Computer communications
Area of application fr
Téléinformatique
Research subject code
2700
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Information technology
Research subject fr
Technologie de l'information
Installment
inst:3
Partie
1
Nb partie
5
Application title
Attraction, Repulsion, and Facility Location
Application summary
My main objective is to investigate algorithms and basic mathematics for attraction and repulsion, with a focus on facility location problems. Attraction (also known as beacon attraction) was recently introduced by Biro with substantial other work from Kostitsnya and Kouhestani. In this model, an activated beacon will cause all particles to move directly towards it, or to slide along a wall if that brings it closer to the beacon. (Here the particles model robots, or messages in a network.) Bose and I introduced a corresponding notion of repulsion. The attraction relation includes visibility, and visibility has a rich theory with many algorithms and combinatorial results. Finding counterparts of these results for attraction is a wide open and exciting new direction, but it also encounters difficulties, often to do with the fact that attraction is not a symmetric relation, whereas visibility is. It is thus ripe for serious study. The study of repulsion encounters even more difficulties than attraction. Visibility and attraction are relations amongst two points (point a can see point b, or a can attract b), and thus their problem formulations and some methodology regarding them are derived from graph theory. Repulsion is a relation amongst three points: point a can repulse point b to some third point c. Therefore even the usual problem formulations may not apply; this makes the area of repulsion particularly interesting. I intend to employ classic computational geometry methodology in my investigation of these topics. This involves studying the basic geometry and combinatorial properties of the relations and designing algorithms that use these properties to answer questions about particular situations. For example, one particular problem that I will investigate is how to preprocess a polygonal domain D so that one may efficiently answer questions of the form: given an attraction beacon b and a point p in D, where does the point p move to if we activate the beacon b? Here, we also get a meaningful question if we replace the attraction beacon with a repulsion actuator. The intended research is a mix of basic research (studying the geometric and combinatorial properties of these relations) and applied research (designing algorithms to answer relevant questions). There are at least three possible application areas of this study. The first is in message routing in sensor networks; the idea of greedy geographical routing is a discretization of attraction. The second application would be in robotics, to understand the behaviour of a robot operating to move towards (attraction) or away from (repulsion) a homing beacon. A third application might be in modelling crowd behaviour, where there may be stimuli of attraction (a place where everyone wants to be) and repulsion (a place that everyone wants to get away from, such as a fire).