## 1 Introduction
### The Query Model  
To facilitate comparisons with earlier results, we adopt much of the notation used by [PERSON] et al. [1] and [PERSON] et al. [2]. Let \(\mathcal{E}\) be a set \(\{e_{1},e_{2},\ldots,e_{n}\}\) of (mobile) entities. Each entity \(e_{i}\) is modeled as a \(d\)-dimensional closed ball with fixed extent and bounded speed, whose position (center location) at any time is specified by the (unknown) continuous function \(\zeta_{i}\) from \([0,\infty)\) (time) to \(\mathbb{R}^{d}\). We take the entity radius to be our _unit of distance_, and take the time for an entity moving at maximum speed to move a unit distance to be our _unit of time_. The \(n\)-tuple \((\zeta_{1}(t),\zeta_{2}(t),\ldots,\zeta_{n}(t))\) is called the _\(\mathcal{E}\)-configuration_ at time \(t\). Entities \(e_{i}\) and \(e_{j}\) are said to _encroach_ upon one another at time \(t\) if the distance \(\|\zeta_{i}(t)-\zeta_{j}(t)\|\) between their centers is less than some fixed _encroachment threshold_\(\Xi\). For simplicity we assume to start that the distance between entity centers is always at least 2, i.e., the _separation_\(\|\zeta_{i}(t)-\zeta_{j}(t)\|-2\) between entities \(e_{i}\) and \(e_{j}\) at time \(t\), is always at least zero--so entities never properly intersect, and that the encroachment threshold is exactly 2 (i.e., we are only concerned with avoiding entity contact). The concluding section considers a relaxation (and decoupling) of these assumptions in which \(\|\zeta_{i}(t)-\zeta_{j}(t)\|\) is always at least some positive constant \(\rho_{0}\) (possibly less than 2), and the encroachment threshold \(\Xi\) is some constant at least \(\rho_{0}\). We wish to maintain knowledge of the positions of the entities over time by making location queries to individual entities, each of which returns the exact position of the entity at the time of the query. A _(query) scheme_\(\mathbb{S}\) is just an assignment of location queries to time instances. We measure the performance of a scheme over a specified time interval \(T\) as the minimum query _granularity_ (the time between consecutive queries) over \(T\). At any time \(t\geq 0\), let \(p_{i}^{\mathbb{S}}(t)\) denote the time, prior to \(t\), that entity \(e_{i}\) was last queried; we define \(p_{i}^{\mathbb{S}}(0)=-\infty\). The _uncertainty region_ of \(e_{i}\) at time \(t\), denoted \(u_{i}^{\mathbb{S}}(t)\), is defined as the ball with center \(\zeta_{i}(p_{i}^{\mathbb{S}}(t))\) and radius \(1+t-p_{i}^{\mathbb{S}}(t)\); note that \(u_{i}^{\mathbb{S}}(0)\) is unbounded. (We omit \(\mathbb{S}\) when it is understood and the dependence on \(t\) when \(t\) is fixed.) Figure 1 illustrates the uncertainty regions of four unit-radius entities shown at their most recently known locations, four, three, two and one time unit in the past, respectively. The set \(U(t)=\{u_{1}(t),\ldots,u_{n}(t)\}\) is called the _(uncertainty) configuration_ at time \(t\). Entity \(e_{i}\) is said to _potentially encroach_ upon entity \(e_{j}\) in configuration \(U(t)\) if \(u_{i}(t)\cap u_{j}(t)\
eq\emptyset\) (that is, there are potential locations for \(e_{i}\) and \(e_{j}\) at time \(t\) such that \(e_{i}\cap e_{j}\
eq\emptyset\)). In this way, any configuration \(U\) gives rise to an associated (symmetric) _potential encroachment graph_\(PE^{U}\) on the set \(\mathcal{E}\). Note, that by our assumptions above, the potential encroachment graph associated with the initial uncertainty configuration \(U(0)\) is complete. We define the following notions of _congestion potential_ (called _interference potential_ in [2]) in terms of configuration \(U\) and the graph \(PE^{U}\). * The **(uncertainty) max-degree** (hereafter **degree**) of the configuration \(U\) is given by \(\delta^{U}=\max_{i}\{\delta^{U}_{i}\}\) where \(\delta^{U}_{i}\) is defined as the degree of entity \(e_{i}\) in \(PE^{U}\) (the maximum number of entities \(e_{j}\), _including_\(e_{i}\), that potentially encroach upon \(e_{i}\) in configuration \(U\)).