## 3 Query Optimization to Obtain Bounded Congestion at a Fixed Target Time
### The Fixed-Target-Time-Degree (FTT-Degree) Query Scheme  
This somewhat more involved query scheme shows that for any \(\Delta\), \(0\leq\Delta\leq x\), uncertainty degree at most \(x~{}+~{}\Delta\) can be guaranteed at a fixed target time using minimum query granularity that is at most \(\Theta(\frac{x}{1+\Delta})\) smaller than that used by any query scheme that guarantees uncertainty degree at most \(x\). As before, since the projected uncertainty regions of all entities are unbounded at time 0, any scheme, including a clairvoyant scheme, must query all but \(x\) of the entities at least once in order to avoid degree (and also ply) greater than \(x\) at the target time. The FTT-degree\([x~{}+~{}\Delta]\) scheme starts by querying all entities in a single round using query granularity \(\frac{x}{2n}\), which is \(O(1)\)-competitive, assuming \(n-(x~{}+~{}\Delta)=\Omega(x~{}+~{}\Delta)\), with what must be conducted by any other scheme. At this point, the FTT-degree\([x~{}+~{}\Delta]\) scheme identifies two sets of entities (i) the \(n_{1}\) entities that are not yet \((x~{}+~{}\Delta)\)-degree-safe (the _unsafe survivors_), and (ii) the \(m_{1}\) entities that are \((x~{}+~{}\Delta)\)-degree-safe and whose projected uncertainty region intersects the projected uncertainty region of one or more of the unsafe survivors (the _safe survivors_). All other entities are set aside and attract no further queries. The scheme then queries, in a second round, all \(n_{1}+m_{1}\) survivors using query granularity \(\frac{\tau}{4(n_{1}+m_{1})}\). In general, after the \(r\)th round, the scheme identifies \(n_{r}\) unsafe survivors and \(m_{r}\) safe survivors, which, assuming \(n_{r}+m_{r}>0\), continue into an \((r+1)\)st round using granularity \(\frac{\tau}{2^{r+1}(n_{r}+m_{r})}\). The \(r\)th round completes at time \(\tau~{}-~{}\tau/2^{r}\). Furthermore, all entities that have not been set aside have a projected uncertainty region whose radius is in the range \((1+\tau/2^{r},1+\tau/2^{r-1}]\). Theorem 3.1: _For any \(\Delta\), \(0\leq\Delta\leq x\), the FTT-degree\([x~{}+~{}\Delta]\) query scheme guarantees uncertainty degree at most \(x~{}+~{}\Delta\) at target time \(\tau\) and uses minimum query granularity over the interval \([0,\tau]\) that is at most a factor \(\Theta(\frac{x}{1+\Delta})\) smaller than the intrinsic fixed-target granularity for guaranteeing uncertainty degree at most \(x\)._  
Proof: We claim that any query scheme \(\mathbb{S}\) that guarantees the uncertainty degree at most \(x\) at time \(\tau\) must use at least \(\Theta(\frac{(n_{r}+m_{r})(1+\Delta)}{x+\Delta})\) queries after the start of the \(r\)th query round of the FTT-degree\([x~{}+~{}\Delta]\) query scheme; any fewer queries would result in one or more entities having a degree greater than \(x\) at the target time. To see this, observe first that each of the \(n_{r}\) unsafe survivors must be _satisfied_; they are either queried by \(\mathbb{S}\) after the start of the \(r\)th query round or have their projected uncertainty degree reduced below \(x\) by at least \(1~{}+~{}\Delta\) queries to their projected uncertainty neighbors after the start of the \(r\)th query round. Assuming that fewer than \(n_{r}/2\) unsafe survivorsare queried by \(\mathbb{S}\) after the start of the \(r\)th query round, we argue that at least \(\frac{m_{r}(1+\Delta)}{2\cdot 4^{d}(x+\Delta)}\) queries must be made after the start of the \(r\)th query round to reduce below \(x\) the projected uncertainty degree of the remaining unsafe survivors. Note, that any query after the start of the \(r\)th round to an entity set aside in an earlier round cannot serve to lower the projected uncertainty degree of any of the \(n_{r}\) unsafe survivors. As in the proof of Theorem 3.1, any query to one of the survivors of the \((r-1)\)st round can serve to decrease by one the projected uncertainty degree of at most \(4^{d}(x\ +\ \Delta)\) of the unsafe survivors whose uncertainty degree is at most \(x\ +\ \Delta\).