## 3 Query Optimization to Obtain Bounded Congestion at a Fixed Target Time
### The Fixed-Target-Time-ply (FTT-ply) Query Scheme  
This query scheme shows that, for any \(\Delta,0\leq\Delta\leq x\), uncertainty ply 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 (even clairvoyant) query scheme that guarantees uncertainty ply at most \(x\). Assuming no prior knowledge about entity locations, we treat the uncertainty regions of all entities as being unbounded at time \(0\). Hence, none of the entities are \((x\ +\ \Delta)\)-ply-safe to start (assuming \(x\ +\ \Delta<n\)). Thus any scheme, including a clairvoyant scheme, must query all but \(x\) of the entities at least once in order to avoid ply greater than \(x\) at the target time. The FTT-ply\([x\ +\ \Delta]\) scheme starts by querying all entities in a single round using query granularity \(\frac{\tau}{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-ply\([x\ +\ \Delta]\) scheme identifies the set of \(n_{1}\) entities that are not yet \((x\ +\ \Delta)\)-ply-safe (the _unsafe survivors_). All other entities are set aside and attract no further queries. The scheme then queries, in a second round, all \(n_{1}\) survivors using query granularity \(\frac{\tau}{4n_{1}}\). In general, after the \(r\)th round, the scheme identifies \(n_{r}\) unsafe survivors which, assuming \(n_{r}>0\), continue into an \((r+1)\)st round using granularity \(\frac{\tau}{2^{r+1}n_{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}]\). Note that, by our assumption, \(x>X_{d}\) and hence, \(c_{d,x}>0\). Thus, since the projected uncertainty region radius of all entities is less than \(1+c_{d,x}/2\), by the time \(r>\lg(\tau/c_{d,x})+2\), no unsafe survivors remain after by the end of round \(\lg(\tau/c_{d,x})+2\). Theorem 1: _For any \(\Delta,0\leq\Delta\leq x\), the FTT-ply\([x\ +\ \Delta]\) query scheme guarantees uncertainty 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 ply at most \(x\)._  
Proof: We claim that any query scheme \(\mathbb{S}\) that guarantees uncertainty ply at most \(x\) at time \(\tau\) must use at least \(\Theta(\frac{n_{r}(1+\Delta)}{x+\Delta})\) queries after the start of the \(r\)th query round of the FTT-ply\([x\ +\ \Delta]\) query scheme; any fewer queries would result in one or more entities having ply greater than \(x\) at the target time. To see this observe first that each of the \(n_{r}\) unsafe survivors is either queried by \(\mathbb{S}\) after the start of the \(r\)th query round or has its projected uncertainty ply reduced to at most \(x\), by queries to at least \(1\ +\ \Delta\) of its projected uncertainty neighbors after the start of the \(r\)th query round. Assuming that fewer than \(n_{r}/2\) unsafe survivors are queried by \(\mathbb{S}\) after the start of the \(r\)th query round, we argue that at least \(\frac{n_{r}(1+\Delta)}{2\cdot 4^{d}(x+\Delta)}\) queries must be made after the start of the \(r\)th query round to reduce the projected uncertainty ply of the remaining unsafe survivors to some value at most \(x\). 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 ply of any of the \(n_{r}\) unsafe survivors. Furthermore, any query to one of the survivors of the \((r-1)\)st round can serve to decrease by one the projected uncertainty ply of at most \(4^{d}(x~{}+~{}\Delta)\) of the unsafe survivors whose projected uncertainty ply is at least \(x~{}+~{}\Delta\).