Attraction, Repulsion, and Facility Location

我的主要目标是研究吸引和排斥的算法和基本数学，重点是设施位置问题。吸引力（也被称为灯塔吸引力）最近由比罗与kostisnya和Kouhestani的大量其他作品一起引入。在这个模型中，激活的信标将导致所有粒子直接向它移动，或者沿着墙壁滑动，如果这使它更靠近信标。（这里的粒子模拟机器人，或者网络中的信息。）玻色和我引入了一个对应的斥力概念。吸引关系中包含可见性，可见性理论丰富，有许多算法和组合结果。寻找与这些结果相对应的吸引力是一个非常开放和令人兴奋的新方向，但它也遇到困难，通常与吸引力不是对称关系这一事实有关，而可见性是。因此，进行认真研究的时机已经成熟。研究排斥比研究吸引遇到的困难还要多。可见性和吸引力是两点之间的关系（点a可以看到点b，或点a可以吸引点b），因此它们的问题表述和一些方法都是从图论中衍生出来的。斥力是三点之间的关系：点a可以将点b排斥到第三点c。因此，即使通常的问题表述也可能不适用；这使得斥力区域特别有趣。我打算在我对这些主题的研究中采用经典的计算几何方法。这包括研究关系的基本几何和组合性质，并设计使用这些性质来回答有关特定情况的问题的算法。例如，我要研究的一个特殊问题是如何预处理一个多边形域D，这样人们就可以有效地回答这样的问题：给定一个吸引信标b和D中的一个点p，如果我们激活信标b，点p会移动到哪里？在这里，我们也得到了一个有意义的问题，如果我们把吸引信标换成排斥致动器。预期的研究是基础研究（研究这些关系的几何和组合性质）和应用研究（设计算法来回答相关问题）的混合。这项研究至少有三个可能的应用领域。首先是传感器网络中的消息路由；贪婪地理路径的思想是吸引力的离散化。第二个应用将在机器人技术中，了解机器人的行为，以操作靠近（吸引）或远离（排斥）一个归航信标。第三个应用可能是群体行为建模，其中可能存在吸引（每个人都想去的地方）和排斥（每个人都想离开的地方，比如火）的刺激。

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