Uncertainty in Geometric Graphs

提出的研究重点是由实体之间的几何关系定义的图，例如移动代理之间的距离。通常情况下，这些实体的位置并不精确，而且，就像移动代理的情况一样，可能会随着时间的推移而改变。这种不确定性允许实体之间可能存在并不真正存在的关系。在通信网络的情况下，关系表示发送直接消息的能力，代理试图将消息发送到现在超出其通信距离的代理时会浪费资源。假设可以获得单个代理的真实位置并每秒向所有代理广播，如何选择这个单一位置以避免浪费消息？这个场景可以建模为一个几何图形。假设每个移动代理具有相同的最大速度，并且可以在2D空间中向任何方向移动，则代理的当前位置位于磁盘中的任何位置，其中心为代理的最后已知位置，其半径为其速度乘以自获得其位置以来的时间。如果两个这样的磁盘（扩展到公共通信距离的一半）相交，则相应的代理可能能够交换直接消息。如果我们考虑这样一个图，它的顶点是代理，它的边连接着磁盘相交的代理，那么这个图的最大程度就是任何代理需要发送的直接消息的最大数量，以到达所有可能的接收者。找到一个代理的真实位置会通过减小该代理的磁盘大小来修改这个交集图。同时，所有其他磁盘都在增长，因为这些其他代理的可能位置增加了。我建议研究算法，以决定如何选择查询哪些几何实体，以获得有关其不确定性区域的更精确信息（例如前面示例中的磁盘），总体目标是优化相关的几何图（例如相交图）属性，如最大度，色数，最大团大小等。查询无论是在查询所需的时间上还是在获取的信息位数上都是代价高昂的，这使得在每个步骤中选择要查询的内容具有挑战性。我们对几何不确定性的看法对于评估图形的几何表示也很有用。使用几何对象绘制图形可能比另一种更可取，如果它允许顶点对象位置的较大扰动或不确定性，同时保留它所表示的图形。例如，如果矩形的相对较小的增加改变了图形，则图形的矩形可见性表示可能更难以解释。研究涉及图论、图表示、不确定输入、运动的不确定性、几何构型的容差，甚至分布式算法等方面。

The proposed research focuses on graphs that are defined by geometric relationships between entities, such as the distance between mobile agents. It is often the case that the location of these entities is not precisely known and, as in the case of mobile agents, can change over time. This uncertainty permits the possibility of relationships between entities that may not truly exist. In the case of communication networks, where the relationship represents the ability to send a direct message, agents waste resources trying to send messages to agents that are now beyond their communication distance. Suppose that the true location of a single agent may be obtained and broadcast to all agents every second, how would this single location be chosen to avoid wasted messages? This scenario may be modelled as a geometric graph. Assuming that each mobile agent has the same maximum speed and can move in any direction in 2D space, the agent's current location lies anywhere in a disk whose centre is the agent's last known location and whose radius is its speed multiplied by the time since its location was obtained. If two such disks (expanded by half the common communication distance) intersect, the corresponding agents may be able to exchange direct messages. If we consider the graph whose vertices are the agents and whose edges connect agents whose disks intersect, the maximum degree of this graph is the maximum number of direct messages any agent needs to send to reach all its possible recipients. Finding the true location of an agent modifies this intersection graph by decreasing the size of that agent's disk. Meanwhile, all other disks grow since the possible locations of these other agents increases. I propose to study algorithms for deciding how to choose which geometric entities to query to obtain more precise information about their uncertainty regions (e.g. the disks in the previous example) with an overall goal of optimizing an associated geometric graph (e.g. intersection graph) property, like maximum degree, chromatic number, maximum clique size, etc. The fact that queries are costly, either in the time required to make the query or in the number of bits of information obtained, makes the choice of what to query at each step challenging. Our perspective of geometric uncertainty is useful as a way to evaluate geometric representations of graphs as well. A drawing of a graph using geometric objects may be preferable to another if it allows larger perturbations or uncertainty in the location of the vertex objects while preserving the graph it represents. For example, a rectangle visibility representation of a graph may be more difficult to interpret if relatively small increases in the rectangles change the graph. The research involves aspects of graph theory, graph representation, uncertain inputs, uncertainty due to motion, tolerance of geometric configurations, and even distributed algorithms.