We consider the problem of using location queries to monitor the congestion potential among a collection of entities moving, with bounded speed but otherwise unpredictably, in $d$-dimensional Euclidean space. Uncertainty in entity locations due to potential motion between queries gives rise to a space of possible entity configurations at each moment in time, with possibly very different congestion properties. We define different measures of what we call the congestion potential of such spaces, in terms of the (dynamic) intersection graph of the uncertainty regions associated with entities, to describe the congestion that might actually occur. Previous work [SoCG'13, EuroCG'14, SICOMP'16, SODA'19], in the same uncertainty model, addressed the problem of minimizing congestion potential using location queries of some bounded frequency. It was shown that it is possible to design a query scheme that is $O(1)$-competitive, in terms of worst-case congestion potential, with other, even clairvoyant query schemes (that know the trajectories of all entities), subject to the same bound on query frequency. In this paper we address the dual problem: how to guarantee a fixed bound on congestion potential while minimizing the query frequency, measured in terms of total number of queries or the minimum spacing between queries (granularity), over any fixed time interval. This complementary objective necessitates quite different algorithms and analyses. Nevertheless, our results parallel those of the earlier papers, specifically tight competitive bounds on required query frequency, with a few surprising differences.
翻译:我们考虑了使用定位查询来监测以约束速度但又无法预测的以美元维度的欧几里德空间移动的一组实体的拥堵潜力的问题。由于在质询之间可能发生运动,实体地点的不确定性导致每个时刻都出现可能的实体配置空间,可能存在非常不同的拥堵特性。我们从与实体相关的不确定区域(动态)交叉图的角度界定了这些空间的拥堵潜力的不同计量方法,以描述可能实际发生的拥堵。以前的工作[SoCG'13, EuroC'G'14, SICOMP'16, SODA'19],在同一不确定性模型中,用某些受限频率的地点查询解决了将拥堵潜力最小化的问题。我们用最坏的拥堵可能性来设计一个叫作O(1)美元竞争性的查询方案,用其他的(知道所有实体的轨迹)查询方法,以相同的紧凑紧频率为对象。在本文中,我们用这种固定的频率查询方法解决了双重问题:如何在最短的频率上保证最短的间隔之间,同时测量任何固定的间隔,同时测量任何固定的频率查询方法。