## 4 Towards Query Optimization to Maintain Bounded Congestion Continuously
### Initializing Accurate Perception of \(x\)-Separation  
To obtain the preconditions of Proposition 1, we could assume that all entities are queried very quickly using low granularity for a short initialization phase. We next show how to use a modified version of the FTT scheme of Section 3 to obtain these preconditions using granularity that is competitive with any scheme that guarantees uncertainty degree at most \(x\) from time \(t_{0}\) onward. **Lemma 1**: _For any \(\Delta,0\leq\Delta\leq x\), and any target time \(t_{0}\geq 0\), there exists an initialization scheme that guarantees_  
_(i)_ \(\sigma_{i}(x\ +\ \Delta,t_{0})/2\leq\widetilde{\sigma}_{i}(x\ +\ \Delta,t_{0})\leq 3 \sigma_{i}(x\ +\ \Delta,t_{0})/2\)_, and_  
_(ii)_ \(t_{0}-p_{i}(t_{0})\leq\lambda_{d,x}\widetilde{\sigma}_{i}(x\ +\ \Delta,p_{i}(t_{0}))/12\)_._  
_using minimum query granularity over the interval \([0,t_{0}]\) that is at most \(\Theta(\frac{x+\Delta}{1+\Delta})\) smaller than the minimum query granularity, over the interval \([0,(a+1)t_{0}]\), used by any other scheme that guarantees uncertainty degree at most \(x\) in the interval \([t_{0},(a+1)t_{0}]\), where \(a=64/(5\lambda_{d,x})\)._  
Proof. : The FTT\([x\ +\ \Delta]\) scheme described in Section 3 is modified as follows: Instead of conducting each successive query round-robin within half of the time remaining to the target time, we use just a fraction \(1/16\) of the time remaining. This means that with each successive round-robin phase, the time remaining to the target decreases by a factor \(b=15/16\). We say that an entity is \((x\ +\ \Delta)\)_-degree-super-safe_ at time \(t_{0}-b^{s}t_{0}\) (i.e., \(b^{s}t_{0}\) units before the target time) if its projected uncertainty region at that time is separated by distance at least \(ab^{s}t_{0}\) from the projected uncertainty regions of all but at most \(x\ +\ \Delta-1\) other entities (so that its \((x\ +\ \Delta)\)-separation at the target time is guaranteed to be at least \(ab^{s}t_{0}\)). This ensures that when \(e_{i}\) is declared \((x\ +\ \Delta)\)-degree-super-safe both the true and perceived \((x\ +\ \Delta)\)-separation of \(e_{i}\) at the target time are at least \(ab^{s}t_{0}\) (no matter what further queries are performed). Assuming that \(e_{i}\) is \((x\ +\ \Delta)\)-degree-super-safe at time \(b^{s}t_{0}\) before the target but not at time \(b^{s-1}t_{0}\) before the target, both the true and perceived \((x\ +\ \Delta)\)-separation of \(e_{i}\) at the target time are at most \((a/b+4/b^{2})b^{s}t_{0}\). Indeed, at time \(b^{s-1}t_{0}\) before target, the separation of surviving projected uncertainty regions is at most \(ab^{s-1}t_{0}\), and while the \(x\)-separation at the target time could be more than this, it cannot be more than four times the radius of any surviving uncertainty region (which is less than \(b^{s-2}t_{0}\)) plus \(ab^{s-1}t_{0}\). Since \((a/b+4/b^{2})b^{s}t_{0}<(16a/15+5)b^{s}t_{0}\), it follows that (i) \(\widetilde{\sigma}_{i}(x\ +\ \Delta,t_{0})\leq\frac{16a/15+5}{\sigma_{i}(x\ +\ \Delta,t_{0})}\), and (ii) \(t_{0}-p_{i}(t_{0})\leq\frac{16}{15a}\widetilde{\sigma}_{i}(x\ +\ \Delta,p_{i}(t_{0}))\). Choosing \(a\) large enough (\(a\geq 64/(5\lambda_{d,x})\) suffices) guarantees the desired properties. Following the analysis of the FTT\([x\ +\ \Delta]\) scheme, if the \(s\)th query round uses \(q_{s}\) queries then any query that guarantees uncertainty degree at most \(x\) at time \(t_{0}+ab^{s}t_{0}/2<(a+1)t_{0}\) must use at least \(\Theta(\frac{q_{s}(1+\Delta)}{x\ +\ \Delta})\) queries between time \(t_{0}-b^{s-1}t_{0}\), the start of the \(s\)th query round, and time \(t_{0}-ab^{s}t_{0}/2\); otherwise, some entity that was not \((x\ +\ \Delta)\)-degree-super-safe at time \(t_{0}-b^{s-1}t_{0}\) would not be \(x\)-safe at time \(t_{0}+ab^{s}t_{0}/2\).