Attraction, Repulsion, and Facility Location

点击翻译按钮获取中文摘要

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).