## 3 Query Optimization to Obtain Bounded Congestion at a Fixed Target Time
### The Fixed-Target-Time-Degree (FTT-Degree) Query Scheme
Thus, any scheme that guarantees uncertainty degree at most \(x\) at time \(\tau\) must make at least \(\frac{n_{r}(1+\Delta)}{2\cdot 4^{d}(x+\Delta)}\) queries after the start of the \(r\)th query round. Similarly, observe that each of the \(m_{r}\) safe survivors must have each of its unsafe neighbors satisfied in the sense described above. But, since the projected uncertainty regions of all survivors are within a factor of 2 in size, each query that serves to lower the projected uncertainty degree of an unsafe neighbor of some safe survivor \(e_{i}\) must be to an entity \(e_{j}\) that has the projected uncertainty region of \(e_{i}\) in its projected uncertainty _near-neighborhood_ (the ball centered at \(z_{j}\), whose radius is nine times the projected uncertainty radius of \(e_{j}\)). But \(e_{j}\) has at most \(18^{d}(x\ +\ \Delta)\) such safe near-neighbours, since any collection of \(18^{d}\hat{x}\) unit radius balls that are all contained in a ball of radius 18, must have a degree (and also ply) at least \(\hat{x}\). It follows that, even if a query to \(e_{j}\) lowers the projected uncertainty degree of all of the unsafe neighbors of \(e_{i}\), a total of at least \(\frac{m_{r}(1+\Delta)}{18^{d}(x+\Delta)}\) queries must be made after the start of the \(r\)th query round by any scheme that guarantees uncertainty degree at most \(x\) at time \(\tau\). Thus, query scheme \(\mathbb{S}\) must use at least  
\[\max\biggl{\{}\frac{n_{r}(1\ +\ \Delta)}{2\cdot 4^{d}(x\ +\ \Delta)},\ \frac{m_{r}(1\ +\ \Delta)}{18^{d}(x\ +\ \Delta)}\biggr{\}}\geq\frac{n_{r}+m_{r}}{2\cdot(18)^{d}}\frac{1\ +\ \Delta}{x\ +\ \Delta}\geq\frac{n_{r}+m_{r}}{4\cdot(18)^{d}}\frac{1\ +\ \Delta}{x}\]  
queries over the interval \([\tau-\tau/2^{r-1},\tau]\). It follows that our query scheme is \(\Theta(\frac{x}{1+\Delta})\)-competitive, in terms of minimum query granularity, with any, even clairvoyant, query scheme that guarantees the uncertainty degree at most \(x\) at the target time. The competitive factor in both of the preceding theorems is worst-case optimal. Specifically, the following example demonstrates that, for \(0\leq\Delta<x\) degree at most \(x\) can be guaranteed at a fixed target time by a clairvoyant scheme that uses query granularity, yet any non-clairvoyant scheme that guarantees ply at most \(x\ +\ \Delta\) at the target time must use the query granularity that is \(O(\frac{x}{\Gamma+\Delta})\). **Example 1**. : _Imagine a configuration involving two collections \(A\) and \(B\) each with \((x+1+\Delta)/2\) point entities located in \(\mathbb{R}^{1}\), on opposite sides of a point \(O\). At time \(0\) all of the entities are at distance \(x+3+3\Delta\) from \(O\), but have unbounded uncertainty regions. All entities begin by moving towards \(O\) at unit speed, but at time \(x+1+\Delta\) a subset of \(1+\Delta\) entities in both \(A\) and \(B\) (the special entities) change direction and move away from \(O\) at unit speed, while all of the others carry on until the target time \(x+3+3\Delta\) when they simultaneously reach \(O\) and stop (cf. Figure 3)._  
_To avoid an uncertainty degree greater than \(x\) at the target time a clairvoyant scheme needs only to (i) query all entities (in arbitrary order) up to time \(x+1+\Delta\), and then (ii) query just the special entities (in arbitrary order) in the next \(2(1+\Delta)\) time prior to the target, using query granularity \(1\), since doing so will leave the uncertainty regions of the \((x+1+\Delta)/2\) entities in \(A\) disjoint from the uncertainty regions of the \(1+\Delta\) special entities in \(B\), and vice versa._  
_On the other hand, to avoid ply \(x+1+\Delta\) at the target time any non-clairvoyant scheme must query at least one of the special entities (in either \(A\) or \(B\)) in the last \(2(1+\Delta)\) time before the target.