## 1 Introduction
### Related Work  
One of the most widely-studied approaches to computing functions of moving entities uses the _kinetic data structure_ model which assumes precise information about the future trajectories of the moving entities and relies on elementary geometric relations among their locations along those trajectories to certify that a combinatorial structure of interest, such as their convex hull, remains essentially the same. The algorithm can anticipate when a relationship will fail, or is informed if a trajectory changes, and the goal is to update the structure efficiently in response to these events [4; 5; 6]. Another less common model assumes that the precise location of _every_ entity is given to the algorithm periodically. The goal again is to update the structure efficiently when this occurs [7; 8; 9].  
More similar to ours is the framework introduced by [PERSON] [10; 11] for studying data in motion problems that require repeated computation of a function (geometric structure) of data that are moving continuously in space where data acquisition via queries is costly. There, location queries occur simultaneously in batches, triggered by requests ([PERSON] refers  
Figure 1: Uncertainty regions (light grey) of four unit-radius entities (dark grey) with uncertainty ply three (witnessed by point \(*\)).  
to these requests as \"queries\") to compute some specified function at some time (unknown in advance) rather than by a requirement to maintain a structure or property at all times. Performance is compared to a \"lucky\" algorithm that queries the minimum amount to calculate the function. [PERSON]'s model and use of competitive evaluation are common to much of the work on query algorithms for uncertain inputs (see [PERSON] and [PERSON]'s survey [12]).  
As mentioned, our model is essentially the same as the one studied by [PERSON] et al. [1] and by [PERSON] et al. [2], both of which focus on point entities. Like the current paper, paper [1] contains strategies whose goal is to guarantee competitively low congestion potential, compared to any other (even clairvoyant) scheme, at one specified target time. It provides precise descriptions of the impact of this guarantee using several measures of initial location knowledge and available lead time before the target. The other paper [2] contains a scheme for guaranteeing competitively low congestion potential at _all_ times. For this more challenging task, the scheme maintains congestion potential over time that is within a constant factor of that maintained by any other scheme over modest-sized time intervals. All of these results dealt with _optimizing congestion potential measures subject to fixed query frequency_.  
In this paper, we consider the complementary problem: _optimizing query frequency required to guarantee fixed bounds on congestion_. These two problems are fundamentally different: being able to optimize congestion using fixed query frequency provides little insight into how to optimize query frequency to maintain a fixed bound on congestion. In particular, even for stationary entities, a small change in the congestion bound can lead to an arbitrarily large change in the required query frequency. Our frequency optimization involves maximizing the minimum query granularity which requires more than just minimizing the number of queries made over a specified interval.