## 3 Query Optimization to Obtain Bounded Congestion at a Fixed Target Time
### The Fixed-Target-Time-Degree (FTT-Degree) Query Scheme
Since special and non-special entities are indistinguishable before this time interval, at least \(x/2+1\) entities in at least one of \(A\) or \(B\) must be queried in the last \(2(1+\Delta)\) time before the target in order to be sure that at least one special entity is queried late enough to confirm that its uncertainty region will not contain \(O\) at the target time. This requires query granularity at most \(\frac{4(1+\Delta)}{x+2}\). Thus, in the worst case every scheme that achieves uncertainty ply at most \(x~{}+~{}\Delta\) at the target time needs to use at least a factor \(\Theta(\frac{\pi}{1+\Delta})\) smaller query granularity in some instances than the best query scheme for achieving uncertainty degree at most \(x\) at the target time on those same instances._  
Theorems 1 and 2 speak to the query frequency requirements for bounding congestion at a fixed target time, measured in terms of ply or degree individually. This leaves open the question of how these measures relate to one another. The following example demonstrates that in some cases the granularity required to bound congestion degree by \(x~{}+~{}\Delta\) can be a factor \(\Theta(\frac{\pi}{1+\Delta})\) smaller than that required to bound congestion ply by \(x\). **Example 2**. : _The example involves two clusters \(A\) and \(B\) of \((x+1+\Delta)/2\) point entities separated by distance \(4(1~{}+~{}\Delta)\). To maintain the uncertainty ply at most \(x\) it suffices to query \(1~{}+~{}\Delta\) entities in both clusters once every \(2(1~{}+~{}\Delta)\) steps, which can be achieved with query frequency one. Since the uncertainty regions associated with queried entities in cluster \(A\) never intersect the uncertainty regions associated with queried entities in cluster \(B\), the largest possible ply involves entities in one cluster (say \(A\)) together with unqueried entities in the other cluster (\(B\)), for a total of \(x\)._  
_On the other hand, to maintain degree at most \(x~{}+~{}\Delta\) no uncertainty region can be allowed to have radius \(4(1~{}+~{}\Delta)\). Thus, all \(x+1+\Delta\) entities need to be queried with frequency at least \(1/\left(4(1~{}+~{}\Delta)\right)\), giving a total query demand of \(x+1+\Delta\) over any time interval of length \(4(1~{}+~{}\Delta)\)._  
Nevertheless, bounding congestion degree at a fixed target time cannot be too much worse than bounding congestion ply. **Theorem 3**. : _The FTT-degree[\(x~{}+~{}\Delta\)] scheme uses a query granularity that is at most a factor \(\frac{\pi^{2}}{\Gamma+\Delta}\) smaller than the best, even clairvoyant, scheme that guarantees ply at most \(x\)._  
Proof. : In the FTT-degree[\(x~{}+~{}\Delta\)] scheme, \(m_{r}\) (the number of safe survivors in round \(r\)) is \(O(n_{r}(x~{}+~{}\Delta))\). Thus, the \"extra\" queries (to handle the safe survivors) are at most a factor \(x~{}+~{}\Delta\) more numerous than the queries to handle the unsafe survivors. Suppose that FTT-ply[\(x~{}+~{}\Delta\)] is modified so that the queries in round \(r\) occur with granularity \(\frac{\tau}{2^{r+1}n_{r}}\) (i.e., half of their previous granularity), completing at the midpoint of the round, and that FTT-degree[\(x~{}+~{}\Delta\)] is modified so that the queries in round \(r\) occur with granularity \(\frac{\tau}{2^{r+1}(n_{r}+m_{r})}\) (i.e., half of their previous granularity), starting at the midpoint of the round. Since the queries of FTT-degree[\(x~{}+~{}\Delta\)] in round \(r\) now occur after the corresponding queries in FTT-ply[\(x~{}+~{}\Delta\)], it is straightforward to see that the unsafe survivors in round \(r\) of FTT-degree[\(x~{}+~{}\Delta\)] are no more numerous than the unsafe survivors in round \(r\) of FTT-ply[\(x~{}+~{}\Delta\)]. It follows that the granularity of the queries in FTT-degree[\(x~{}+~{}\Delta\)] is no more than a factor \(\Theta(x~{}+~{}\Delta)\) smaller than that of FTT-ply[\(x~{}+~{}\Delta\)].