Uncertainty in Geometric Graphs

几何图形中的不确定性

• 批准号: RGPIN-2022-04449
• 负责人: Evans, William
• 金额: $ 2.11万
• 依托单位: University of British Columbia
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=749812
• 关键词: Uncertainty; Geometric; Graphs

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.

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