Dept. of Computer Science, University of British Columbia, Vancouver, Canada
<EMAIL_ADDRESS>Dept. of Computer Science, University of British Columbia,
Vancouver, Canada<EMAIL_ADDRESS>William Evans and David Kirkpatrick Theory of
computation Computational geometry Theory of computation Online algorithms

# Frequency-Competitive Query Strategies to Maintain Low Congestion Potential
Among Moving Entities††thanks: This work was partially funded by NSERC
Discovery Grants

William Evans  David Kirkpatrick

###### Abstract

We consider the problem of using location queries to monitor the congestion
potential among a collection of entities moving, with bounded speed but
otherwise unpredictably, in $d$-dimensional Euclidean space. Uncertainty in
entity locations due to potential motion between queries gives rise to a space
of possible entity configurations at each moment in time, with possibly very
different congestion properties. We define different measures of what we call
the congestion potential of such spaces, in terms of the (dynamic)
intersection graph of the uncertainty regions associated with entities, to
describe the congestion that might actually occur.

Previous work [SoCG’13, EuroCG’14, SICOMP’16, SODA’19], in the same
uncertainty model, addressed the problem of minimizing congestion potential
using location queries of some bounded frequency. It was shown that it is
possible to design a query scheme that is $O(1)$-competitive, in terms of
worst-case congestion potential, with other, even clairvoyant query schemes
(that know the trajectories of all entities), subject to the same bound on
query frequency.

In this paper we address the dual problem: how to guarantee a fixed bound on
congestion potential while minimizing the query frequency, measured in terms
of total number of queries or the minimum spacing between queries
(granularity), over any fixed time interval. This complementary objective
necessitates quite different algorithms and analyses. Nevertheless, our
results parallel those of the earlier papers, specifically tight competitive
bounds on required query frequency, with a few surprising differences.

Earlier work identified a natural application in channel minimization for
mobile transmitters, expressed in terms of the chromatic number of the
intersection graph of uncertainty regions. In this paper, we suggest another
natural application in collision avoidance, expressed in terms of the maximum
vertex degree of the intersection graph, another of our congestion potential
measures. Our query scheme uses within a constant factor of the minimum query
frequency to certify that, at all times, every entity is free of imminent
collision with all but some pre-specified number of other entities.

###### keywords:

data in motion, uncertain inputs, online algorithms

##  1 Introduction

We consider problems associated with the uncertainty of entity locations
arising from entity motion that is unmonitored and only speed-limited. Our
model permits entities to be queried at any time in order to reveal their true
location. We want to understand with what frequency such queries need to be
performed, and which entities should be queried, in order to maintain a
particular measure of the congestion potential of the entities formulated in
terms of the overlap of their uncertainty regions. We present query schemes to
maintain several measures of congestion potential that are competitive in
terms of the frequency of their queries over all modest-sized time intervals
with any scheme that maintains the same measure.

###  1.1 The Query Model

Let $\mathcal{E}$ be a set $\\{e_{1},e_{2},\dots,e_{n}\\}$ of (mobile)
entities. Each entity $e_{i}$ is modelled as a $d$-dimensional closed ball
with fixed extent (radius) $\rho$, and position (center location) specified by
the (unknown) function $\zeta_{i}$ from $[0,\infty)$ (time) to
$\mathbb{R}^{d}$. The $n$-tuple
$(\zeta_{1}(t),\zeta_{2}(t),\dots,\zeta_{n}(t))$ is called the _$\mathcal{E}$
-configuration_ at time $t$. Entity $e_{i}$ can move at most one unit of
distance in one unit of time.111The concluding section considers a
generalization In which entity $e_{i}$ has an upper bound $s_{i}$ on its
speed. The _separation_ between entities $e_{i}$ and $e_{j}$ at time $t$ is
given by $\|\zeta_{i}(t)-\zeta_{j}(t)\|-2\rho$.

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 _query complexity_ of a scheme over a specified time interval $T$
in terms of the total number of queries over $T$ as well as the minimum query
_granularity_ (the time between consecutive queries) over $T$.

At any time $t\geq 0$, let $p^{\mathbb{S}}_{i}(t)$ denote the time, prior to
$t$, that entity $e_{i}$ was last queried; we define
$p^{\mathbb{S}}_{i}(0)=-\infty$. The _uncertainty region_ of $e_{i}$ at time
$t$, denoted $u^{\mathbb{S}}_{i}(t)$, is defined as the ball with center
$\zeta_{i}(p^{\mathbb{S}}_{i}(t))$ and radius $\rho+t-p^{\mathbb{S}}_{i}(t)$.
(Note that $u^{\mathbb{S}}_{i}(0)$ has unbounded radius.) We omit $\mathbb{S}$
when it is understood and the dependence on $t$ when $t$ is fixed.

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)\neq\emptyset$ (that is, there are potential locations for $e_{i}$ and
$e_{j}$ at time $t$ such that $e_{i}\cap e_{j}\neq\emptyset$). In this way any
configuration $U$ gives rise to an associated (symmetric) _potential
encroachment graph_ $\mathit{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_ in terms of
configuration $U$ and the graph $\mathit{PE}^{U}$:

  * •

the (uncertainty) 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 $\mathit{PE}^{U}$ (the maximum number of
entities $e_{j}$, _including $e_{i}$_, that potentially encroach upon $e_{i}$
in configuration $U$.)

  * •

the (uncertainty) ply $\omega^{U}$ of configuration $U$ is the maximum number
of uncertainty regions in $U$ that intersect at a single point. This is the
largest number of entities in configuration $U$ whose mutual potential
encroachment is witnessed by a single point.

  * •

the (uncertainty) thickness $\chi^{U}$ of configuration $U$ is the chromatic
number of $\mathit{PE}^{U}$. This is the size of the smallest decomposition of
$\mathcal{E}$ into independent sets (sets with no potential for encroachment)
in configuration $U$. The chromatic number and clique number of ball
intersection graphs, in any fixed dimension $d$, are the same up to a constant
factor.

Note that $\omega^{U}\leq\chi^{U}\leq\delta^{U}$, so upper bounds on
$\delta^{U}$, and lower bounds on $\omega^{U}$, apply to all three measures.

We assume throughout that the separation between entities is non-negative,
i.e. the entities never properly intersect.222The concluding section considers
a relaxation of this assumption where entity centres never get closer than
some constant fraction of $\rho$ apart. This assumption is helpful since it
means that if uncertainty regions are kept sufficiently small, uncertainty ply
can be kept to at most two. Similarly, for $x$ larger than some dimension-
dependent constant, it is always possible to maintain uncertainty degree at
most $x$.

###  1.2 Related Work

One of the most widely-studied approaches to computing functions of moving
entities uses the _kinetic data structure_ model which assumes precise
information about the future trajectories of the moving entities and relies on
elementary geometric relations among their locations along those trajectories
to certify that a combinatorial structure of interest, such as their convex
hull, remains essentially the same. The algorithm can anticipate when a
relation will fail, or is informed if a trajectory changes, and the goal is to
update the structure efficiently in response to these events [13, 2, 14].
Another less common model assumes that the precise location of _every_ entity
is given to the algorithm periodically. The goal again is to update the
structure efficiently when this occurs [5, 6, 7].

More similar to ours is the framework introduced by Kahan [16, 17] for
studying data in motion problems that require repeated computation of a
function (geometric structure) of data that is moving continuously in space
where data acquisition via queries is costly. There, queries occur
simultaneously in batches, triggered by requests333Kahan calls these
“queries”. to compute some function at some time rather than by a requirement
to maintain a structure or property at all times. Performance is compared to a
“lucky” algorithm that queries the minimum amount to calculate the function.
Kahan’s model and use of competitive evaluation is common to much of the work
on query algorithms for uncertain inputs (see Erlebach and Hoffmann’s survey
[8]).

Our model is essentially the same as the one studied by Evans et al. [11]
(which unifies and improves [9, 10]) and by Busto et al. [3]. Paper [11]
contains schemes whose goal is to guarantee competitively low congestion
potential, compared to any other (even clairvoyant) scheme, at one specified
target time. It provides precise descriptions of the impact on this guarantee
for several measures of initial location knowledge and available lead time
before the target. The other paper [3] contains a scheme for guaranteeing
competitively low congestion potential at _all_ times. For this more
challenging task the scheme maintains congestion potential over time that is
within a constant factor of that maintained by any other scheme over modest-
sized time intervals. All of these results dealt with the optimization of
congestion potential measures subject to fixed query frequency. In this paper,
we consider the dual problem: optimizing query frequency required to guarantee
fixed bounds on congestion. This optimization takes two forms: minimizing
total queries (over specified intervals) and then maximizing the minimum query
granularity. Our schemes are competitive in the first respect, even compared
with clairvoyant schemes, and use granularity that is competitive to what is
required if entities remained stationary in the future.

###  1.3 Our Results

After establishing some geometric properties of clustered entities, we
describe a query scheme to achieve uncertainty degree at most $x$ at a fixed
target time in the future whose number of queries and query granularity are at
most a factor $\Theta(x)$ smaller than that used by any, even clairvoyant,
query scheme to achieve the same goal. If we instead allow our scheme
uncertainty degree at most $(1+\beta)x$ for $\beta>0$, the competitive factor
drops to $\Theta(\frac{(1+\beta)x}{1+\beta x})$. We show that both of these
competitive factors are best-possible.

We then turn our attention to maintaining fixed potential congestion measures
at all times (the _continuous_ case). At first, we imagine that entities
remain stationary, even though they have the potential to move, since this
avoids complications arising from entities changing location and nearby
neighbors. We show a (tight) factor gap of $\Theta(\ln n)$ between the
frequency required to achieve uncertainty degree (or ply) $x$ at a fixed-time
versus at all times for $n$ stationary entities. We then define a stationary
frequency demand that lower bounds the frequency of queries used by any scheme
to maintain uncertainty ply $x$ and describe a scheme using $\Theta(x)$ times
that frequency to achieve uncertainty degree $x$ over large enough time
intervals. Again the competitive factor drops if we relax our scheme to
maintain degree $(1+\beta)x$. Both competitive factors are best-possible.

When the entities are mobile, the stationary frequency demand changes over
time as entities cluster and separate. We obtain a corresponding (cumulative)
intrinsic query frequency to maintain ply $x$ by integrating the stationary
measure over a time interval $T$. Any scheme must use at least this many
queries over $T$ to maintain ply $x$ (even if it is allowed to exceed ply $x$
outside of $T$). We describe a query scheme that can maintain uncertainty
degree $x$ at all times and uses a factor $\Theta(x)$ more queries (and
correspondingly smaller granularity). Yet again, the competitive factor drops
when we only need to maintain degree $(1+\beta)x$, and in all cases is best
possible.

Not surprisingly, it is possible to further strengthen our competitive bounds
by making assumptions about the uniformity of entity distributions. In the
concluding discussion, we discuss some ways in which uniformity impacts our
results.

As an application of our model (mentioned in [3]) consider a set of entities
that are transmission sources, with associated transmission ranges, moving in
two or higher dimensions. Two such entities, transmitting on the same channel,
interfere if their transmission ranges intersect. Uncertainty in the location
of a transmission source effectively expands its transmission range to a
potential transmission range, and the chromatic number of the intersection
graph of these potential transmission ranges, our uncertainty thickness
measure, gives the minimum number of transmission channels required to avoid
potential transmission interference. Optimizing the frequency of location
queries to maintain a fixed bound on the number of channels (the objective in
this paper) seems to be at least as well motivated as optimizing the number of
channels for a fixed query frequency (the objective in the earlier work).

Another natural application of the results in this paper concerns collision
avoidance for mobile entities. In this case, by maintaining uncertainty degree
at most $x$, we maintain for each entity $e_{i}$ a certificate identifying
the, at most $x-1$, other entities that could potentially collide with $e_{i}$
(those warranting more careful local monitoring).

##  2 Geometric Preliminaries

Let $Z=(z_{1},z_{2},\ldots,z_{n})$ be any $\mathcal{E}$-configuration in
dimension $d$. For any positive integer $x$, we denote by $\sigma^{Z}_{i}(x)$
the separation between $e_{i}$ and its $x$th closest neighbor (not including
$e_{i}$) in configuration $Z$, and by $B^{Z}_{i}(x)$ the closed ball with
radius $r^{Z}_{i}(x)=\sigma^{Z}_{i}(x)+\rho$ and center $z_{i}$. We refer to
$B^{Z}_{i}(x)$ as the _$x$ -ball_, to $\sigma^{Z}_{i}(x)$ as the _$x$
-separation_, and to $r^{Z}_{i}(x)$ as the _$x$ -radius_, of $e_{i}$ in
configuration $Z$. Let $\Gamma^{Z}_{i}(x)$ denote the set of at most $x$
entities (including $e_{i}$) in $\mathcal{E}$ that intersect (as balls) the
interior of $B^{Z}_{i}(x)$. We will omit $Z$ when the configuration is
understood. Note that, for all entities $e_{i}$ and $e_{j}$,

$r_{j}^{Z}(x)\leq\rho+2r_{i}^{Z}(x)\mbox{ and
}\sigma_{j}^{Z}(x)\leq\|z_{j}-z_{i}\|+\sigma_{i}^{Z}(x),$ (1)

since the ball with radius $\rho+\|z_{j}-z_{i}\|+w$ centered at $z_{j}$
contains the ball with radius $\rho+w$ centered at $z_{i}$ (by the triangle
inequality).

We first establish an elementary but nevertheless critical property
(generalizing Lemma 2.1 from [3]) of configurations of $x$-balls that relates
to extremal cases of their relative congestion. The $\alpha$-inflation of the
$x$-ball $B^{Z}_{i}(x)$ is the closed ball, denoted $\alpha B^{Z}_{i}(x)$ with
radius $\alpha r^{Z}_{i}(x)$ and center $z_{i}$.

Let $A_{d,\alpha}$ be the maximum number of vectors in dimension $d$ that have
angle separation at least $2\arcsin(\frac{1}{4\alpha})$. See Conway and Sloane
[4] for bounds on $A_{d,\alpha}$.

######  Lemma .

Let $\alpha\geq 1$. In any $\mathcal{E}$-configuration $Z$, any ball $B$
intersects the $\alpha$-inflated $x$-balls of at most $A_{d,\alpha}x$ entities
whose $x$-balls have a radius at least as large as that of $B$.

###### Proof.

Let $B$ be a ball with center $z_{B}$ and radius $r_{B}$, and let
$E\subseteq\mathcal{E}$ be the set of entities $e_{i}$ whose $\alpha$-inflated
$x$-ball $\alpha B^{Z}_{i}(x)$ intersects $B$ and whose radius $\alpha
r^{Z}_{i}(x)$ is at least $r_{B}$. We construct a subset $I\subseteq E$
incrementally by (i) selecting the un-eliminated entity $e_{i}\in E$ with the
largest $x$-radius, (ii) eliminating all entities in $\Gamma^{Z}_{i}(x)$
(including $e_{i}$ itself) from $E$, and (iii) repeating, until $E$ is empty.
It follows that (i) since we eliminate in non-increasing order of $x$-radius,
for all $e_{i}\in I$, the interior of $B^{Z}_{i}(x)$ intersects only one
entity from $I$ (namely, $e_{i}$), (ii) since $\Gamma^{Z}_{i}(x)$ contains at
most $x$ entities from $E$, $|I|\geq|E|/x$, and (iii) if $|I|>1$ then none of
the entities in $I$ have the same center as $B$.

Suppose that $|I|>1$; otherwise $|E|\leq x$, and nothing remains to be proved.
Let $e_{i}$ and $e_{j}$ be any two distinct elements of $I$. Then
$2\|z_{i}-z_{j}\|>2\max\\{r^{Z}_{i}(x),\;r^{Z}_{j}(x)\\}\geq
r^{Z}_{i}(x)+r^{Z}_{j}(x)\geq\max\\{r^{Z}_{i}(x)+r_{B},\;r^{Z}_{j}(x)+r_{B}\\}\geq\max\\{\|z_{i}-z_{B}\|,\;\|z_{j}-z_{B}\|\\}/\alpha$.
Thus, the vector $v_{i}$ from $z_{B}$ to $z_{i}$ and the vector $v_{j}$ from
$z_{B}$ to $z_{j}$ must form an angle greater than $2\arcsin(1/(4\alpha))$. It
follows that $|I|\leq A_{d,\alpha}$, and hence $|E|\leq A_{d,\alpha}x$. ∎

We have assumed that entities do not properly intersect. Define $c_{d,x}$ to
be the smallest constant such that a unit-radius $d$-dimensional ball $B$ can
have $x$ disjoint unit-radius $d$-dimensional balls (including itself) with
separation from $B$ at most $c_{d,x}$. Thus, $\sigma^{Z}_{i}(x)\geq
c_{d,x}\rho$ and hence

$\rho\leq\frac{1-\lambda_{d,x}}{\lambda_{d,x}}\sigma_{i}^{Z}(x)\mbox{ and
}r_{i}^{Z}(x)\leq\sigma_{i}^{Z}(x)/\lambda_{d,x}$ (2)

where $\lambda_{d,x}=\frac{c_{d,x}}{1+c_{d,x}}$. Observe that $c_{d,x}$ is at
least $\xi\geq 0$, for $x\geq(3+\xi)^{d}$ since unit-radius balls with
separation at most $\xi$ from $B$ must all fit within a ball of radius $3+\xi$
concentric with $B$. Thus $1/2\leq\lambda_{d,x}<1$ if $x\geq 4^{d}$.

Let $\hat{x}_{d}$ be the largest value of $x$ for which $c_{d,x}=0$ (e.g.,
$\hat{x}_{2}=7$). Clearly, if $x\leq\hat{x}_{d}$ there are entity
configurations $Z$ with $\sigma^{Z}_{i}(x)=0$. Thus, for such $x$, maintaining
uncertainty degree at most $x$ might be impossible in general, for any query
scheme. On the other hand, if $x>\hat{x}_{d}$, then $0<\lambda_{d,x}<1$. Thus:

######  Remark 2.1.

Hereafter we will assume that $x$, our bound on congestion potential, is
greater than $\hat{x}_{d}$. The constants $\hat{x}_{d}$ and $\lambda_{d,x}$
will play a role in both the formulation and analysis of our query schemes.

##  3 Query Optimization at a Fixed Target Time

Suppose our goal, for a given entity set $\mathcal{E}$, is to optimize queries
to guarantee low congestion potential at a fixed target time, say time $\tau$
in the future. One reason might be to prepare for a computation at that time
whose efficiency depends on this low congestion potential [18]. Not
surprisingly, this can also play a role in initializing our query scheme that
optimizes queries continuously from some point in time onward.

Since we assume unbounded uncertainty regions at the start, any query scheme
must query at least a fixed fraction of the entities over the interval
$[0,\tau]$, provided $\mathcal{E}$ is sufficiently large compared to the
allowed potential congestion measure. Hence the minimum query granularity over
this interval must be $O(\tau/|\mathcal{E}|)$. Furthermore, if granularity is
not an issue, $O(|\mathcal{E}|)$ queries suffice, provided they are made
sufficiently close to the target time. Optimizing the minimum query
granularity is less straightforward. Nevertheless, it is clear that any
sensible query scheme (one that avoids redundant queries), using minimum query
granularity $\gamma$, that guarantees a given measure of congestion potential
at most $x$ at the target time $\tau$, determines a radius $\rho+k_{i}\gamma$,
for each entity $e_{i}\in\mathcal{E}$, where (i) $k_{1},k_{2},\ldots k_{n}$ is
a permutation of $1,2,\ldots n$, and (ii) the uncertainty configuration, in
which entity $e_{i}$ has an uncertainty region $u_{i}$ with center
$\zeta_{i}(\tau)$ and radius $\rho+k_{i}\gamma$, has the given congestion
measure at most $x$. For any measure, we associate with $\mathcal{E}$ an
intrinsic fixed-target granularity, denoted $\gamma_{\mathcal{E},x},$ defined
to be the largest $\gamma$ for which these conditions are satisfiable.

It should be clear that, if entities are stationary, the intrinsic fixed-
target granularity, for any congestion measure, can in principle be realized,
up to a factor of two, by a scheme that first queries all of the entities,
until half of the time to the target has expired (using granularity
$\frac{\tau}{2|\mathcal{E}|}$) and then optimizes, with respect to the given
congestion measure, taking advantage of the knowledge of entity positions.

Despite the fact that realizing the intrinsic fixed-target granularity exactly
is NP-hard (this follows directly from Theorem 2.2 of [9]), for stationary
entities it is straightforward to achieve degree at most $x$ at a fixed target
time using query granularity that is within a constant factor of the intrinsic
fixed-target granularity. This follows from the observations that (i) every
entity must be queried within time corresponding to its $x$-separation, prior
to the target time, in order to achieve degree at most $x$ at the target time,
and (ii) if every entity is queried within time corresponding to a fraction
$h$ of its $x$-separation, prior to the target time, then the uncertainty
degree at the target time is guaranteed to be at most $x$, provided
$h<\lambda_{d,x}/3$. (The latter follows because any entity $e_{j}$ that is
not an $x$-neighbour of entity $e_{i}$ must have $\sigma_{j}(x)\leq
2\sigma_{i}(x)+2\rho$, by equation (1), and hence, using equation (2),
$h(\sigma_{i}(x)+\sigma_{j}(x))\leq(h(\lambda_{d,x}+2)/\lambda_{d,x})\sigma_{i}(x)\leq\sigma_{i}(x)$.)

Guaranteeing that a particular measure of congestion potential is at most some
specified value $x$ at the fixed target time $\tau$ is obviously more of a
challenge for mobile entities. We define the projected uncertainty region of
an entity, at any moment in time, to be the uncertainty region for that entity
that would result if the entity experiences no further queries before the
target time. We say that an entity is $x$-ply-safe at a particular time if its
projected uncertainty region has no point in common with the projected
uncertainty regions of more than $x-1$ other entities (so that it could not
possibly have uncertainty ply exceeding $x$ at the target time). Similarly, we
say that an entity is $x$-degree-safe at a particular time if its projected
uncertainty region intersects the projected uncertainty regions of at most
$x-1$ other entities (so that its $x$-separation at the target time is
guaranteed to be positive).

The following Fixed-Target-Time(FTT) query scheme shows that uncertainty
degree at most $(1+\beta)x$ can be guaranteed at a fixed target time using
minimum query granularity that is at most $\Theta(\frac{(1+\beta)x}{1+\beta
x})$ smaller than that used by any query scheme that guarantees uncertainty
degree at most $x$. Since the uncertainty regions of all entities are
unbounded at time $0$, none of the entities are $(1+\beta)x$-degree-safe to
start (assuming $(1+\beta)x<n$). Furthermore 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$[(1+\beta)x]$
scheme starts by querying all entities in a single round using query
granularity $\tau/(2n_{0})$, which is $O(1)$-competitive, assuming
$n-(1+\beta)x=\Omega((1+\beta)x)$, with what must be done by any other scheme.

At this point, the FTT$[(1+\beta)x]$ scheme identifies two sets of entities
(i) the $n_{1}$ entities that are not yet $(1+\beta)x$-degree-safe (the
_unsafe survivors_), and (ii) the $m_{1}$ entities that are
$(1+\beta)x$-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.

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 robin, 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
robin using granularity $\frac{\tau}{2^{r+1}(n_{r}+m_{r})}$. It should be
clear that the $r$th round robin 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
$(\rho+\tau/2^{r},\rho+\tau/2^{r-1}]$. (From the latter it follows, by a
straightforward area argument, that the projected uncertainty region of any
survivor, though it may intersect the projected uncertainty region of many
other survivors, intersects $O((1+\beta)x)$ uncertainty regions whose
projected uncertainty degree among themselves is at most $(1+\beta)x$.)

######  Theorem 3.1.

The FTT$[(1+\beta)x]$ query scheme guarantees uncertainty degree at most
$(1+\beta)x$ at target time $\tau$ and uses minimum query granularity over the
interval $[0,\tau]$ that is at most a factor $\Theta(\frac{(1+\beta)x}{1+\beta
x})$ smaller than $\gamma_{\mathcal{E},x}$.

######  Proof 3.2.

We claim that any query scheme $\mathbb{S}$ must use at least
$\Theta(\frac{(n_{r}+m_{r})(1+\beta x)}{(1+\beta)x})$ queries after the start
of the $r$th query round; any fewer queries would result in one or more
entities having degree 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 degree reduced below $(1+\beta)x$ by at least $1+\beta
x$ queries to its projected uncertainty neighbours after the start of the
$r$th query round. Since 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, and, as previously
observed, any query to one of the survivors of the $(r-1)$st round can serve
to lower (below $(1+\beta)x$) the projected uncertainty degree of at most
$\Theta((1+\beta)x)$ of the safe survivors, it follows that any scheme must
make at least $\Theta(\frac{n_{r}(1+\beta x)}{(1+\beta)x})$ queries after the
start of the $r$th query round.

Similarly, observe that each of the $m_{r}$ safe survivors must have each of
its unsafe neighbours satisfied in the sense described above. But each query
that serves to lower the projected uncertainty degree of an unsafe neighbour
of some safe survivor $e_{i}$ must be to an entity $e_{j}$ that has the
projected uncertainty region of $e_{i}$ in its projected uncertainty _near-
neighbourhood_ (the ball centered at $e_{j}$, whose radius is nine times the
projected uncertainty radius of $e_{j}$). But since $e_{j}$ has at most
$\Theta((1+\beta)x)$ such safe near-neighbours (by another straightforward
area argument) it follows that, even if a query to $e_{j}$ lowers the
projected uncertainty degree of all of the unsafe neighbours of $e_{i}$, a
total of at least $\Theta(\frac{m_{r}(1+\beta x)}{(1+\beta)x})$ queries must
be made by any scheme after the start of the $r$th query round.

Thus, query scheme $\mathbb{S}$ must use at least $\Theta(\frac{(1+\beta
x)(n_{r}+m_{r})}{(1+\beta)x})$ queries over the interval
$[\tau-\tau/2^{r-1},\tau]$. It follows that our query scheme is
$\Theta(\frac{(1+\beta)x}{1+\beta x})$-competitive, in terms of maximum query
granularity, with any, even clairvoyant, query scheme that guarantees
uncertainty degree at most $x$ at the target time.

A similar, though somewhat simpler, argument shows that a competitive ratio of
$\Theta(\frac{(1+\beta)x}{1+\beta x})$ on the granularity for a scheme that
achieves _ply_ at most $(1+\beta)x$, relative to any, even clairvoyant, scheme
that guarantees ply at most $x$, can also be achieved. The only difference,
besides substituting projected ply for projected degree, and $(1+\beta)x$-ply-
safe for $(1+\beta)x$-degree-safe, is the observation that all entities that
have become $(1+\beta)x$-ply-safe can be set aside (i.e. there is no need to
retain $(1+\beta)x$-ply-safe as survivors) since additional queries to such
entities cannot serve to reduce the number of not-yet $(1+\beta)x$-safe
entities. Thus the preceding argument holds with all $m_{r}=0$.

It is interesting to see that the $O(\frac{(1+\beta)x}{1+\beta x})$
competitive ratio on query granularity for achieving degree at most
$(1+\beta)x$ (as well as that for achieving ply at most $(1+\beta)x$) at a
fixed target time cannot be improved in general. In fact, we show in Appendix
B an example demonstrating that, for any $\beta\geq 0$, degree at most
$(1+\beta)x$ can be guaranteed at a fixed target time by a scheme that uses
query granularity one, yet any scheme that guarantees ply at most $x$ at the
target time must use at least $(1+2\beta)x+1$ queries over the last $2(1+\beta
x)$ steps.

##  4 Continuous Query Optimization: Stationary Entities

For stationary entities, maintaining a fixed configuration $Z$ over time,
uncertainty degree at most $x$ can be maintained on a continuous basis using
granularity at least $\Theta(\frac{1}{\ln n})$ times what we called the
intrinsic fixed-target granularity ($\gamma_{\mathcal{E},x}$), required to
achieve uncertainty degree at most $x$ at any fixed time. This follows because
the uncertainty region of each entity $e_{i}$ can be kept, at all times,
within its corresponding fixed-target realization, simply by querying it at
least once every $k_{i}\gamma_{\mathcal{E},x}$ time steps. By Corollary 3.2 of
[15], we know that such a schedule is feasible using query granularity
$\gamma_{\mathcal{E},x}/(2\ln n)$. A simple example (see Appendix A) shows
that this $\Theta(\frac{1}{\ln n})$ gap is unavoidable in general.

###  4.1 Intrinsic Frequency Demand: Stationary Entities

If the radius of the uncertainty region $u_{i}$ of $e_{i}\in\mathcal{E}$
exceeds $\rho+\sigma_{i}(x)$ then $u_{i}$ intersects at least $x+1$ entities
in $\mathcal{E}$. Thus $\sigma_{i}(x)$, the $x$-separation of $e_{i}$, is an
upper bound on the amount of uncertainty whose avoidance guarantees that the
uncertainty degree of entity $e_{i}$ remains at most $x$. It follows that, for
stationary entities, each entity $e_{i}$ must be queried with frequency at
least $1/\sigma_{i}(x)$. Hence
$\phi_{\mathcal{E},x}=\sum_{e_{i}\in\mathcal{E}}\frac{1}{\sigma_{i}(x)}$, the
_stationary frequency demand_ , provides a lower bound on the total query
frequency444This frequency demand appears in work on scheduling jobs according
to a vector $v$ of periods, where job $j$ must be scheduled at least once in
every time interval of length $v_{j}$ [15, 12]. required to avoid uncertainty
degree greater than $x$, with entities in stationary configuration $Z$. Note
that, since we have assumed that $x\leq\hat{x}_{d}$, we know that
$\sigma_{i}(x)$ is some strictly positive multiple (at least $\lambda_{d,x}$)
of $r_{i}(x)$ (see Equation (2)). Hence,
$\lambda_{d,x}\phi_{\mathcal{E},x}\leq\sum_{e_{i}\in\mathcal{E}}\frac{1}{r_{i}(x)}$.

The following lemma shows that an expression closely related to
$\phi_{\mathcal{E},x}$ plays an essential role as well in bounding the total
number of queries required to maintain uncertainty ply at most $x$ over a
specified time interval. Note that it applies to strategies that maintain ply
at most $x$ _only_ over $T$, _even if they allow ply greater than $x$
elsewhere_.

######  Lemma 1.

Let $\beta$ be a non-negative constant, and let $T$ be a time interval for
which $|T|\phi_{\mathcal{E},(1+\beta)x}\geq 2|\mathcal{E}|$. Then any query
scheme with maximum uncertainty ply at most $x$ over $T$ must make a total of
at least $\frac{(\beta
x+1)\lambda_{d,(1+\beta)x}}{4(1+\beta)A_{d,1}x}\cdot|T|\phi_{\mathcal{E},(1+\beta)x}$
queries over $T$.

######  Proof 4.1.

Let $\mathcal{E}^{\prime}=\\{e_{i}\in\mathcal{E}\mid
r_{i}((1+\beta)x)\leq|T|\\}$. Then
$|T|\phi_{\mathcal{E}^{\prime},(1+\beta)x}\geq|T|\phi_{\mathcal{E},(1+\beta)x}-|\mathcal{E}|\geq|T|\phi_{\mathcal{E},(1+\beta)x}/2$.

For each $e_{i}\in\mathcal{E}^{\prime}$ partition $T$ into
$\big{\lfloor}\frac{|T|}{r_{i}((1+\beta)x)}\big{\rfloor}\geq\frac{|T|}{2r_{i}((1+\beta)x)}$
sub-intervals each of length at least $r_{i}((1+\beta)x)$. Let $E_{i}$ denote
the set of (at least) $(1+\beta)x$ entities in $\mathcal{E}\setminus e_{i}$
that intersect the $(1+\beta)x$-ball of entity $e_{i}$. We say that entity
$e_{i}$ is _satisfied_ in a sub-interval if at least $\beta x+1$ of the
entities in $E_{i}$ are queried in that sub-interval.

If $e_{i}$ is not satisfied in a given sub-interval then at the end of the
sub-interval at least $x$ of the $(1+\beta)x$ entities in $E_{i}$ must have
uncertainty regions of radius at least $r_{i}((1+\beta)x)$, and hence
intersect $z_{i}$, forming ply at least $x+1$ at that point. Thus, to avoid
ply greater than $x$ throughout $T$, every entity $e_{i}$ must be satisfied in
each of its sub-intervals, and so have associated with it at least $(\beta
x+1)\cdot\frac{|T|}{2r_{i}((1+\beta)x)}$ queries.

But, by Lemma 2 entity $e_{j}$ can be within the $(1+\beta)x$-ball of at most
$(1+\beta)A_{d,1}x$ entities, and so a query to $e_{j}$ can serve to satisfy
at most $(1+\beta)A_{d,1}x$ other entities. It follows that the total number
of queries needed to avoid ply greater than $x$ throughout interval $T$ is at
least

$(\beta
x+1)\cdot\sum_{e_{i}\in\mathcal{E}^{\prime}}\frac{|T|}{2r_{i}((1+\beta)x)}\frac{1}{(1+\beta)A_{d,1}x}\geq\frac{(\beta
x+1)}{2(1+\beta)A_{d,1}x}|T|\sum_{e_{i}\in\mathcal{E}^{\prime}}\frac{1}{r_{i}((1+\beta)x)}\\\
\geq\frac{(\beta
x+1)}{2(1+\beta)A_{d,1}x}\cdot|T|\lambda_{d,(1+\beta)x}\phi_{\mathcal{E}^{\prime},(1+\beta)x}\geq\frac{(\beta
x+1)\lambda_{d,(1+\beta)x}}{4(1+\beta)A_{d,1}x}\cdot|T|\phi_{\mathcal{E},(1+\beta)x}.$

We next show that it is possible to maintain uncertainty degree (and hence
uncertainty ply) at most $x$ using a query scheme with minimum query
granularity that is $\Theta(1/\phi_{\mathcal{E},x})$.

###  4.2 A Scheme to Maintain Low Degree: Stationary Entities

The _Frequency-Weighted Round-Robin_ scheme for maintaining uncertainty degree
at most $x$, denoted ${\rm FWRR}[x]$, queries according to a schedule in
which, for all $i$, entity $e_{i}$ is queried once every

$t_{i}=2^{g+\lfloor\lg[\sigma_{i}(x)\lambda_{d,x}/(\lambda_{d,x}+2)]\rfloor}$
time steps of size (granularity) $1/2^{g}$, where
$g=\lceil\lg(\frac{\lambda_{d,x}+2}{\lambda_{d,x}}\phi_{\mathcal{E},x})\rceil+1$.
The schedule repeats after $\max\\{t_{i}\\}$ steps.

######  Lemma 4.2.

The query scheme ${\rm FWRR}[x]$ maintains uncertainty configurations with
uncertainty degree at most $x$ at all times, and has an implementation using
minimum query granularity at least
$\frac{\lambda_{d,x}}{4(\lambda_{d,x}+2)}\frac{1}{\phi_{\mathcal{E},x}}$.

######  Proof 4.3.

Since $t_{i}/2^{g}\leq\frac{\lambda_{d,x}}{\lambda_{d,x}+2}\sigma_{i}(x)$, it
follows that ${\rm FWRR}[x]$ will query every entity $e_{i}$ with at most
$\frac{\lambda_{d,x}}{\lambda_{d,x}+2}\sigma_{i}(x)$ time between queries.
Equation (1) implies that any entity $e_{j}$ whose separation from $e_{i}$ is
$s\geq\sigma_{i}(x)$ has the property that $\sigma_{j}(x)\leq
s+2\rho+\sigma_{i}(x)\leq 2s+2\rho$. Hence, using equation (2),

$\sigma_{i}(x)+\sigma_{j}(x)\leq
3s+2\rho\leq(3+2\frac{1-\lambda_{d,x}}{\lambda_{d,x}})s=\frac{\lambda_{d,x}+2}{\lambda_{d,x}}s,$

and
$\frac{\lambda_{d,x}}{\lambda_{d,x}+2}\sigma_{i}(x)+\frac{\lambda_{d,x}}{\lambda_{d,x}+2}\sigma_{j}(x)\leq
s$. So the uncertainty regions of $e_{i}$ and $e_{j}$ never properly
intersect, and thus the uncertainty degree of $e_{i}$ remains at most $x$ over
time.

Since
$\sum_{e_{i}\in\mathcal{E}}\frac{1}{t_{i}}<\frac{\lambda_{d,x}+2}{\lambda_{d,x}2^{g-1}}\phi_{\mathcal{E},x}\leq
1$, it follows from a result of Anily et al. [1] (see Lemma 6.2) that a query
schedule exists with at most one query for every slot of size $1/2^{g}$.
Hence, the FWRR query scheme can be implemented with query granularity at
least
$\frac{\lambda_{d,x}}{4(\lambda_{d,x}+2)}\frac{1}{\phi_{\mathcal{E},x}}$.

Combining Lemma 1 with Lemma 4.2 we get:

######  Theorem 4.4.

The ${\rm FWRR}[(1+\beta)x]$ query scheme maintains uncertainty configurations
with uncertainty degree at most $(1+\beta)x$ using minimum query granularity
at least
$\frac{\lambda_{d,x}}{4(\lambda_{d,x}+2)}\frac{1}{\phi_{\mathcal{E},(1+\beta)x}}$.
Furthermore, it uses a total number of queries over any time interval $T$
satisfying $|T|\phi_{\mathcal{E},(1+\beta)x}\geq 2|\mathcal{E}|$, that is
competitive with any scheme $\mathbb{S}$ that maintains uncertainty
configurations with uncertainty ply at most $x$ over $T$, even if $\mathbb{S}$
permits uncertainty ply larger than $x$ elsewhere. The competitive factor is:
(i) $O(x)$, when $\beta=0$, and (ii) $O(\frac{1+\beta}{\beta})$, when
$\beta>0$.

Appendix A describes a collection of stationary entities showing that, for any
$\beta\geq 0$, ply at most $x$ can be maintained with query granularity one,
yet any scheme that guarantees uncertainty degree at most $(1+\beta)x$ must
use at least $(1+\beta)x+1$ queries over any time interval of length
$4(1+\beta x)$.

Thus the worst-case competitiveness of the ${\rm FWRR}[(1+\beta)x]$ query
scheme is asymptotically optimal not only for maintaining low uncertainty
_degree_ , it is also optimal among all strategies that maintain low
uncertainty _ply_ by maintaining low uncertainty degree.

##  5 Continuous Query Optimization: General Mobile Entities

While the case of stationary entities exhibits some of the difficulties in
maintaining uncertainty regions with low congestion, mobile entities add an
additional level of complexity.

Since an $\mathcal{E}$-configuration may now change over time, we add a
parameter $t$ to our stationary definitions, and refer to
$x_{\mathcal{E}}(t)$, $B_{i}(x,t)$, $\sigma_{i}(x,t)$, and $r_{i}(x,t)$ in
place of their stationary counterparts at time $t$, where it is understood
that the configuration in question is just the $\mathcal{E}$-configuration at
time $t$.

The same construction (see Appendix B) used above to bound the competitiveness
of query strategies for achieving low uncertainty degree at a fixed target
time also allows us to conclude essentially the same result in the continuous
case: every scheme that maintains congestion ply at most $x$ at all times
needs to use minimum query granularity over some time interval that is at
least a factor $\frac{(1+2\beta)x+1}{4+4\beta x}$ smaller than that used by
the best query scheme for achieving congestion degree at most $x+\beta x$ at
all times.

As we have seen, when entities are stationary, the expression
$|T|\phi_{\mathcal{E},x}=\sum_{e_{i}\in\mathcal{E}}\frac{|T|}{\sigma_{i}(x)}$,
the stationary frequency demand over time interval $T$, plays a central role
in characterizing the unavoidable number of queries needed to avoid
uncertainty degree (or uncertainty ply) greater than $x$. For mobile entities,
we will refer to the more general expression
$\phi_{\mathcal{E},x}(T)=\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}{t}}{\sigma_{i}(x,t)}$
as the intrinsic frequency demand over time interval $T$, with no risk of
confusion.

###  5.1 Intrinsic Frequency Demand: General Mobile Entities

It follows from earlier work on the optimization of query degree using fixed
query frequency [3] that a high stationary frequency demand at one instant in
time does not necessarily imply that uncertainty degree at most $x$ is
unsustainable. Nevertheless, as the following lemma demonstrates, high
intrinsic frequency demand, over a sufficiently large time interval $T$, does
imply a lower bound on the number of queries over $T$.

######  Lemma 1.

Let $\beta$ be a non-negative constant, and let $T$ be a time interval for
which $\phi_{\mathcal{E},(1+\beta)x}(T)\geq 505|\mathcal{E}|$. Define $T^{+}$
to be the interval $T$ extended by $|T|/2^{55}$. Then any query scheme with
maximum uncertainty ply at most $x$ over $T^{+}$ must make a total of at least
$\frac{(\beta
x+1)\lambda_{d,x}}{75(1+\beta)A_{d,3}x}\phi_{\mathcal{E},(1+\beta)x}(T)=\Theta(\phi_{\mathcal{E},(1+\beta)x}(T))$
queries over $T^{+}$.

######  Proof 5.1.

At a high level the proof parallels that of Lemma 1. For each
$e_{i}\in\mathcal{E}$ partition $T$ into sub-intervals, starting at times
$t_{1}<t_{2}<\cdots$, whose length depends on (i) the $(1+\beta)x$-radius of
$e_{i}$ at the start of the sub-interval, and (ii) the uniformity of the
$(1+\beta)x$-radius of $e_{i}$ throughout the interval. Good sub-intervals
$[t_{j},t_{j+1})$ have length $t_{j+1}-t_{j}=r_{i}((1+\beta)x,t_{j})$ and
satisfy $r_{i}((1+\beta)x,t_{j})/3<r_{i}((1+\beta)x,t)\leq
3r_{i}((1+\beta)x,t_{j})$, for $t_{j}\leq t<t_{j+1}$. Bad sub-intervals
$[t_{j},t_{j+1})$ have length $t_{j+1}-t_{j}\leq r_{i}((1+\beta)x,t_{j})$ and
satisfy
$r_{i}((1+\beta)x,t_{j})/3<r_{i}((1+\beta)x,t)<3r_{i}((1+\beta)x,t_{j})$, for
$t_{j}\leq t<t_{j+1}$, and
$r_{i}((1+\beta)x,t_{j+1})=r_{i}((1+\beta)x,t_{j})/3$. Sub-intervals that end
(prematurely) at the end of $T$ are referred to as terminal sub-intervals.

Note that for all sub-intervals $r_{i}((1+\beta)x,t_{j})/3\leq
r_{i}((1+\beta)x,t)\leq 3r_{i}((1+\beta)x,t_{j})$, for $t_{j}<t\leq t_{j+1}$.
Hence, for good sub-intervals
$1/3\leq\int_{t_{j}}^{t_{j+1}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}<3$,
and for bad sub-intervals
$1/9<\int_{t_{j}}^{t_{j+1}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}<3$.

Thus, if we ignore all terminal sub-intervals and all entities with fewer than
$100$ non-terminal sub-intervals, the sub-intervals of the remaining entities
contribute in total more than
$2/5\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$.
It follows that there must be at least
$2/15\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$
such intervals in total.

Let $e_{i}$ be one of the remaining entities, with $w_{i}\geq 100$ non-
terminal sub-intervals. A bad sub-interval $[t_{j},t_{j+1})$ is matched if
there is a subsequent good sub-interval whose range of $r_{i}((1+\beta)x,t)$
values includes $r_{i}((1+\beta)x,t_{j+1})$. Since the range of
$r_{i}((1+\beta)x,t)$ values for a given good sub-interval is at most twice
its initial value, and the range of $r_{i}((1+\beta)x,t)$ values for a given
bad sub-interval is at least twice its final value, it follows that a good
sub-interval can serve as the earliest match to at most one bad sub-interval.

Suppose that more than $4w_{i}/5$ of the non-terminal sub-intervals of $e_{i}$
over $T$ are unmatched bad intervals. Then $e_{i}$’s sub-interval sequence
must end with a sub-interval of size at most $|T|/3^{4w_{i}/5}$. In this case
consider the continuation of $e_{i}$’s sub-interval sequence into the
remainder of $T^{+}$. If this includes an interval of size $|T|/3^{3w_{i}/5}$
then this extension must include at least $w_{i}/5$ good intervals. But if all
sub-intervals in the continuation are smaller than $|T|/3^{3w_{i}/5}$ then the
unmatched bad intervals among these span less than $2|T|/3^{3w_{i}/5}$, so
there must be at least
$\frac{|T^{+}|-|T|-2|T|/3^{3w_{i}/5}}{|T|/3^{3w_{i}/5}}>w_{i}-2>w_{i}/2$ good
and matched bad intervals over the extension (since
$|T|/3^{55}>w_{i}\cdot|T|/3^{3w_{i}/5}$, when $w_{i}\geq 100$).

Alternatively, at least $w_{i}/5$ of the non-terminal sub-intervals of $e_{i}$
over $T$ are good or matched bad intervals.

In either case, it must be that at least $w_{i}/5$ of the sub-intervals of
$e_{i}$ over $T^{+}$ are either good or matched bad intervals. Hence at least
$w_{i}/10$ of these sub-intervals must be good. Since this is true of all of
the entities with at least $100$ non-terminal sub-intervals, and such entities
have at least
$2/15\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$
non-terminal sub-intervals in total, it follows that there must be at least
$2/150\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$
good sub-intervals in total.

It remains then to follow the argument from the stationary case (Lemma 1),
focusing on good sub-intervals alone, since (a) these are long enough to
support the argument that maintaining ply at most $x$ requires that all but
$x-1$ initial $(1+\beta)x$-neighbours must be queried within the sub-interval
in order to avoid ply greater than $x$, and (b) the $(1+\beta)x$-radius is
sufficiently uniform over these sub-intervals to support the assertion that
any neighbour query can contribute to the demand of at most
$\Theta((1+\beta)x)$ sub-intervals.

If fewer than $\beta x+1$ of the at least $(1+\beta)x+1$ entities (including
$e_{i}$) that intersect the $(1+\beta)x$-ball of $e_{i}$ at the start of a
good sub-interval are not queried in that sub-interval then at the end of that
sub-interval at least $x+1$ of these entities must have uncertainty regions of
radius at least $r_{i}((1+\beta)x)$, and hence intersect at the point occupied
by the center of $e_{i}$ at the start of the sun-interval, forming ply at
least $x+1$ at that point. Thus, to avoid ply greater than $x$ throughout $T$,
every entity $e_{i}$ must have associated with it at least $\beta x+1$ queries
in each of its good sub-intervals. Summing over all good sub-intervals of all
entities this gives a total of at least, at least $\frac{\beta
x+1}{75}\cdot\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$
associated queries.

Of course, as in Lemma 1, a query to some entity $e_{j}$ may serve to satisfy
sub-interval demands for many different entities $e_{i}$. The earlier sharing
argument from Lemma 1 is only slightly complicated by the fact that, at the
time an initial $(1+\beta)x$-neighbor $e_{j}$ is queried it is no longer
necessarily inside the $(1+\beta)x$-ball of all of the entities $e_{i}$ that
it helps satisfy. However, since each entity $e_{i}$ is assumed to have a
$(1+\beta)x$-radius that is at most a factor three larger than it was at the
start of its sub-interval, $e_{j}$ must be inside a 3-inflated
$(1+\beta)x$-ball of each of these other entities at the time $e_{j}$ is
queried. Hence, by Lemma 2, a query to $e_{j}$ can satisfy the demand of good
sub-intervals associated with at most $A_{d,3}(1+\beta)x$ other entities.

It turns out that the lower bound implicit in Lemma 1 holds for the interval
$T$ itself, or a very small shift of $T$:

######  Corollary 2.

Let $\beta$ be a non-negative constant, and let $T$ be a time interval for
which $\phi_{\mathcal{E},(1+\beta)x}(T)\geq 1010|\mathcal{E}|$. Define
$\overrightarrow{T}$ to be the interval $T$ shifted by $|T|/2^{55}$ and
$T^{+}=T\cup\overrightarrow{T}$. Then any query scheme with maximum
uncertainty ply at most $x$ over $T^{+}$ must make a total of at least
$\frac{(\beta
x+1)\lambda_{d,(1+\beta)x}}{75(1+\beta)A_{d,3}x}\phi_{\mathcal{E},(1+\beta)x}(T)=\Theta(\phi_{\mathcal{E},(1+\beta)x}(T))$
queries over either $T$ or $\overrightarrow{T}$.

######  Proof 5.2.

Let $\overleftarrow{T}$ to be the interval $T$ shifted by $-|T|/2^{55}$,
$T_{0}=\overleftarrow{T}\cap T$, and $T_{1}=\overrightarrow{T}\cap T$. Since
$T=T_{0}\cup T_{1}$, either
$\sum_{e_{i}\in\mathcal{E}}\int_{T_{0}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}\geq
1/2\sum_{e_{i}\in\mathcal{E}}\int_{T_{0}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}\geq
505|\mathcal{E}|$ or
$\sum_{e_{i}\in\mathcal{E}}\int_{T_{1}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}\geq
1/2\sum_{e_{i}\in\mathcal{E}}\int_{T_{0}}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}\geq
505|\mathcal{E}|$. But $T_{0}^{+}\subset T$ and
$T_{1}^{+}\subset\overrightarrow{T}$, so any query scheme with maximum
uncertainty ply at most $x$ over $T^{+}$ has maximum uncertainty ply at most
$x$ over both $T_{0}^{+}$ and $T_{1}^{+}$. Hence, by the lemma, any query
scheme with maximum uncertainty ply at most $x$ over $T^{+}$ must make a total
of at least $\frac{(\beta
x+1)}{75(1+\beta)A_{d,3}x}\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)})$
queries over either $T$ or $\overrightarrow{T}$. But, by equation (2),
$\frac{(\beta
x+1)}{75(1+\beta)A_{d}x}\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}\geq\frac{(\beta
x+1)\lambda_{d,(1+\beta)x}}{75(1+\beta)A_{d}x}\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}t}{r_{i}((1+\beta)x,t)}$.

###  5.2 Perception Versus Reality

For any query scheme, the true location of a moving entity $e_{i}$ at time
$t$, $\zeta_{i}(t)$, may differ from its _perceived location_ ,
$\zeta_{i}(p_{i}(t))$, its location at the time of its most recent query. Let
$N_{i}({x},{t})$ be $e_{i}$ plus the set of $x$ entities whose perceived
locations at time $t$ are closest to the perceived location of $e_{i}$ at time
$t$. The _perceived $x$-separation_ of $e_{i}$ at time $t$, denoted
$\widetilde{\sigma}_{i}({x},{t})$, is the separation between $e_{i}$ and its
perceived $x$th-nearest-neighbor at time $t$, i.e.,
$\widetilde{\sigma}_{i}({x},{t})=\max_{e_{j}\in
N_{i}({x},{t})}\|\zeta_{i}(p_{i}(t))-\zeta_{j}(p_{j}(t))\|-2\rho$. The
_perceived $x$-radius_ of $e_{i}$ at time $t$, denoted ${\rm
Phys.\leavevmode\nobreak\ Rev.\leavevmode\nobreak\ D}[t]{x}{i}$, is just
$\rho+\widetilde{\sigma}_{i}({x},{t})$.

Since a scheme only knows the perceived locations of the entities, it is
important that each entity $e_{i}$ be probed sufficiently often that its
perceived $x$-separation $\widetilde{\sigma}_{i}({x},{t})$ closely
approximates its true $x$-separation $\sigma_{i}({x},{t})$ at all times $t$.
The following technical lemma asserts that once a close relationship between
perception and reality has been established, it can be sustained by ensuring
that the time between queries to an entity is bounded by some small fraction
of its perceived $x$-separation.

######  Lemma 3.

Suppose that for some $t_{0}$ and for all entities $e_{i}$,

  1. (i)

$\sigma_{i}({x},{p_{i}(t_{0})})/2\leq\widetilde{\sigma}_{i}({x},{p_{i}(t_{0})})\leq
3\sigma_{i}({x},{p_{i}(t_{0})})/2$, [perception is close to reality for
$e_{i}$ at time $p_{i}(t_{0})$] and

  2. (ii)

for any $t\geq t_{0}$,
$t-p_{i}(t)\leq\lambda_{d,x}\widetilde{\sigma}_{i}({x},{p_{i}(t)})/12$ [all
queries are done promptly based on perception].

Then for all entities $e_{i}$,
$\sigma_{i}({x},{t})/2\leq\widetilde{\sigma}_{i}({x},{t})\leq
3\sigma_{i}({x},{t})/2$, for all $t\geq p_{i}(t_{0})$.

######  Proof 5.3.

We begin by arguing by induction that for all entities $e_{i}$,
$\sigma_{i}({x},{t^{\prime}})/2\leq\widetilde{\sigma}_{i}({x},{t^{\prime}})\leq
3\sigma_{i}({x},{t^{\prime}})/2$ at all times $t^{\prime}\geq t_{0}$ that
entity $e_{i}$ is queried. If this is not true, suppose that $t^{*}$ is the
time of the first query (without loss of generality, to $e_{j}$) after $t_{0}$
at which $\sigma_{j}({x},{t^{*}})/2\leq\widetilde{\sigma}_{j}({x},{t^{*}})\leq
3\sigma_{j}({x},{t^{*}})/2$ does not hold.

Since
$\sigma_{i}({x},{p_{i}(t^{*})})/2\leq\widetilde{\sigma}_{i}({x},{p_{i}(t^{*})})\leq
3\sigma_{i}({x},{p_{i}(t^{*})})/2$, for all entities $e_{i}$, and
$\sigma_{i}({x},{p_{i}(t)})-2(t-p_{i}(t))\leq\sigma_{i}({x},{t})\leq\sigma_{i}({x},{p_{i}(t)})+2(t-p_{i}(t))$,
for $t>p_{i}(t)$, it follows from assumption (ii) that

$t^{*}-p_{i}(t^{*})\leq\frac{\lambda_{d,x}\widetilde{\sigma}_{i}({x},{p_{i}(t^{*})})}{12}\leq\frac{\lambda_{d,x}\sigma_{i}({x},{p_{i}(t^{*})})}{8}\leq\frac{\lambda_{d,x}(\sigma_{i}({x},{t^{*}})+2(t^{*}-p_{i}(t^{*})))}{8}$

which implies
$\frac{4-\lambda_{d,x}}{4}(t^{*}-p_{i}(t^{*}))\leq\frac{\lambda_{d,x}\sigma_{i}({x},{t^{*}})}{8}$
and hence
$t^{*}-p_{i}(t^{*})\leq\frac{\lambda_{d,x}}{8-2\lambda_{d,x}}\sigma_{i}({x},{t^{*}})\leq\frac{\lambda_{d,x}}{6}\sigma_{i}({x},{t^{*}})$
.

Using Equation (1), it follows that

$t^{*}-p_{i}(t^{*})\leq\frac{\lambda_{d,x}(\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|+\sigma_{j}({x},{t^{*}}))}{6}.$

So at time $t^{*}$ every entity $e_{i}$, where $i\neq j$, has been queried
within the last
$\lambda_{d,x}(\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|+\sigma_{i}({x},{t^{*}}))/6$
time steps and has a perceived position within this distance of its actual
position at time $t^{*}$. Since the perceived position of $e_{j}$ may also
differ, by at most $\lambda_{d,x}\sigma_{j}({x},{t^{*}})/6$, from its actual
position at time $t^{*}$, the distance between the perceived locations of
$e_{i}$ and $e_{j}$ at time $t^{*}$ satisfies,

$\displaystyle(1-\lambda_{d,x}/6)$
$\displaystyle\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|-2\lambda_{d,x}\sigma_{j}({x},{t^{*}}))/6$
$\displaystyle\leq\|\zeta_{i}(p_{i}(t^{*}))-\zeta_{j}(p_{j}(t^{*}))\|$
$\displaystyle\leq(1+\lambda_{d,x}/6)\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|+2\lambda_{d,x}\sigma_{j}({x},{t^{*}}))/6$

Since at least $x$ entities $e_{i}$ (the ones, other than $e_{j}$, in
$N_{j}({x},{t^{*}})$) satisfy
$\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|\leq\sigma_{j}({x},{t^{*}})+2\rho$,
these same entities have perceived locations at time $t^{*}$ within distance
$(1+\lambda_{d,x}/6)(\sigma_{j}({x},{t^{*}})+2\rho)+2\lambda_{d,x}\sigma_{j}({x},{t^{*}}))/6=(1+3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})+2(1+\lambda_{d,x}/6)\rho$
of $\zeta_{j}(p_{j}(t^{*}))$. Thus

$\displaystyle\widetilde{\sigma}_{j}({x},{t^{*}})$
$\displaystyle\leq(1+3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})+\lambda_{d,x}\rho/3$
$\displaystyle\leq(1+3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})+(1-\lambda_{d,x})\sigma_{j}({x},{t^{*}})/3$
$\displaystyle\leq(4/3+\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})\leq
3\sigma_{j}({x},{t^{*}})/2.$

On the other hand, since all but at most $x-1$ entities $e_{i}$ satisfy
$\|\zeta_{i}(t^{*})-\zeta_{j}(t^{*})\|\geq\sigma_{j}({x},{t^{*}})+2\rho$,
these same entities have perceived location at time $t^{*}$ at least distance
$(1-\lambda_{d,x}/6)(\sigma_{j}({x},{t^{*}})+2\rho)-2\lambda_{d,x}\sigma_{j}({x},{t^{*}}))/6=(1-3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})+2(1-\lambda_{d,x}/6)\rho$
from $\zeta_{j}(p_{j}(t^{*}))$. Thus

$\displaystyle\widetilde{\sigma}_{j}({x},{t^{*}})$
$\displaystyle\geq(1-3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})-\lambda_{d,x}\rho/3$
$\displaystyle\geq(1-3\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})-(1-\lambda_{d,x})\sigma_{j}({x},{t^{*}})/3$
$\displaystyle\geq(2/3-\lambda_{d,x}/6)\sigma_{j}({x},{t^{*}})\geq\sigma_{j}({x},{t^{*}})/2.$

Taken together these contradict our assumption that
$\sigma_{j}({x},{t^{*}})/2\leq\widetilde{\sigma}_{j}({x},{t^{*}})\leq
3\sigma_{j}({x},{t^{*}})/2$ does not hold, and hence
$\sigma_{i}({x},{t^{\prime}})/2\leq\widetilde{\sigma}_{i}({x},{t^{\prime}})\leq
3\sigma_{i}({x},{t^{\prime}})/2$ at all times $t^{\prime}\geq t_{0}$ that
entity $e_{i}$ is queried.

With this it follows by the same argument as above, replacing $t^{*}$ by an
arbitrary $t^{\prime}\geq p_{i}(t_{0}))$, that
$\sigma_{i}({x},{t^{\prime}})/2\leq\widetilde{\sigma}_{i}({x},{t^{\prime}})\leq
3\sigma_{i}({x},{t^{\prime}})/2$.

To obtain the preconditions of Lemma 3, we could assume that all entities are
queried very quickly using low granularity for a short initialization phase.
Instead, we 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 4.

For any $\beta\geq 0$ and any target time $t_{0}\geq 0$, there exists an
initialization scheme that guarantees

  1. (i)

$\sigma_{i}({(1+\beta)x},{t_{0}})/2\leq\widetilde{\sigma}_{i}({(1+\beta)x},{t_{0}})\leq
3\sigma_{i}({(1+\beta)x},{t_{0}})/2$, and

  2. (ii)

$t_{0}-p_{i}(t_{0})\leq\lambda_{d,x}\widetilde{\sigma}_{i}({(1+\beta)x},{p_{i}(t_{0})})/12$.

using minimum query granularity over the interval $[0,t_{0}]$ that is at most
$\Theta(\frac{(1+\beta)x}{1+\beta x})$ 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}]$.

######  Proof 5.4.

The FTT$[(1+\beta)x]$ 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 $(1+\beta)x$-degree-super-safe at a time $b^{s}t_{0}$
units before the target time $t_{0}$ 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 $(1+\beta)x-1$ other entities (so that
its $(1+\beta)x$-separation at the target time is guaranteed to be at least
$ab^{s}t_{0}$). This ensures that when $e_{i}$ is declared
$(1+\beta)x$-degree-super-safe both the true and perceived
$(1+\beta)x$-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 $(1+\beta)x$-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 $(1+\beta)x$-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 $4$ 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}({(1+\beta)x},{t_{0}})\leq(16a/15+5)/a\;\sigma_{i}({(1+\beta)x},{t_{0}})$,
and (ii) $t_{0}-p_{i}(t_{0})\leq
16\widetilde{\sigma}_{i}({(1+\beta)x},{p_{i}(t_{0})})/(15a)$. Choosing $a$
large enough ($a\geq 64/(5\lambda_{d,x})$ suffices) guarantees the desired
properties.

Following the analysis of the FTT$[(1+\beta)x]$ 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+\beta x)}{(1+\beta)x})$ 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 $(1+\beta)x$-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$. It follows that this initialization scheme uses a
minimum query granularity that is competitive to within a factor of
$\Theta(\frac{(1+\beta)x}{1+\beta x})$ with the minimum granularity used by
any other scheme that guarantees the uncertainty degree is at most $x$,

###  5.3 A Scheme to Maintain Low Degree: General Mobile Entities

A _bucket_ is a set of entities and an associated time interval whose length
(the bucket’s _length_) is a power of two. The $i$th bucket $B$ of length
$2^{b}$ has time interval $T_{B}=[i2^{b},(i+1)2^{b})$, for integers $i$ and
$b$. The time intervals of buckets of the same length partition $[0,\infty)$,
and a bucket of length $2^{b}$ spans exactly $2^{s}$ _sub-buckets_ of length
$2^{b-s}$.

Entities are assigned to exactly one bucket at any moment in time. Membership
of entity $e_{j}$ in a given bucket $B$ implies a commitment to query $e_{j}$
within the interval $T_{B}$. The _basic_ version of the BucketScheme (see Alg.
1) fulfills these commitments by scheduling a query to $e_{j}$ at any time
within that time interval. That is, any version of Schedule($e_{j}$, $B$) that
allocates a query for $e_{j}$ at some time within $T_{B}$ satisfies the basic
BucketScheme. After an entity $e_{j}$ is queried, it is reassigned to a future
bucket in a way that preserves (via Lemma 3) the following invariants: for all
$t^{\prime}\in T_{B}$, (i)
$\sigma_{j}({x},{t^{\prime}})/2\leq\widetilde{\sigma}_{j}({x},{t^{\prime}})\leq
3\sigma_{j}({x},{t^{\prime}})/2$; and (ii)
$\sigma_{j}({x},{t^{\prime}})=\Theta(2^{b})$, so
$\int_{T_{B}}\frac{\mathop{}\\!\mathrm{d}{t}}{\sigma_{i}(x,t)}=\Theta(1)$.

Algorithm 1 BucketScheme$[x]$

1:Assume perception-reality precondition properties hold at time $t_{0}$.
$\triangleright$ See Lemma 4

2:for all entities $e_{j}$ do $\triangleright$ make initial query-time
assignments

3: Assign $e_{j}$ to the first bucket $B$ of length $2^{b}$ starting after
time $t_{0}$, where
$b=\lfloor\lg[(\lambda_{d,x}/24)\widetilde{\sigma}_{j}({x},{t_{0}})]\rfloor$

4: Schedule($e_{j}$, $B$)

5:repeat

6: Advance $t$ to the next query time (of say $e_{j}$)

7: Query $e_{j}$

8: Assign $e_{j}$ to the next bucket $B$ of length $2^{b}$ starting after time
$t+2^{b}$, where
$b=\lfloor\lg[(\lambda_{d,x}/24)\widetilde{\sigma}_{j}({x},{t})]\rfloor$

9: Schedule($e_{j}$, $B$) $\triangleright$ Assign $e_{j}$ a query time in
interval of bucket $B$

######  Theorem 5.5.

The basic BucketScheme$[x]$ maintains uncertainty degree at most $x$
indefinitely. Furthermore, over any time interval $T$ in which the basic
BucketScheme$[x]$ makes $3|\mathcal{E}|$ queries,
$\phi_{\mathcal{E},x}(T)=\Omega(|\mathcal{E}|)$.

######  Proof 5.6.

It is straightforward to confirm that the assignment of entities to buckets
(specified in line 7) ensures that the time between successive queries to any
entity $e_{i}$ satisfies precondition (ii) of Lemma 3. From the proof of Lemma
3 we see that this in turn implies that
$t-p_{i}(t)\leq\frac{\lambda_{d,x}}{6}\sigma_{i}({x},{t})$, for all entities
$e_{i}$ and all $t\geq t_{0}$. But
$\frac{\lambda_{d,x}}{6}\sigma_{i}({x},{t})\leq\frac{\lambda_{d,x}}{\lambda_{d,x}+2}\sigma_{i}(x,t)$,
and so following the identical analysis used in the proof of Lemma 4.2, we
conclude that uncertainty degree at most $x$ is maintained indefinitely.

Since no entity has a query scheduled in overlapping buckets, it follows that
if the basic BucketScheme$[x]$ makes $3|\mathcal{E}|$ queries over $T$ then,
among these, it must make at least $|\mathcal{E}|$ queries to entities in
buckets that are fully spanned by $T$. Since each entity in each fully spanned
bucket contributes $\Theta(1)$ to $\phi_{\mathcal{E},x}(T)$, it follows that
$\phi_{\mathcal{E},x}(T)=\Omega(|\mathcal{E}|)$.

A more fully specified implementation of the BucketScheme is not only
competitive in terms of total queries over reasonably small intervals, but
also competitive in terms of query granularity. The idea of this _refined_
BucketScheme is to replace the simple scheduling policy Schedule of the basic
BucketScheme with a recursive policy Schedule* that generates a refined
reassignment of entities to buckets. Whenever a bucket $B$ of length $2^{b}$
has been assigned two entities, these entities are immediately reassigned to
the two sub-buckets of $B$ of length $2^{b-1}$. In this way, when all
reassignments are finished, all of the entities are assigned to their own
buckets. The entity associated with a bucket $B$ has a _tentative next query
time_ at the midpoint of $B$. Tentative query times are updated of course when
entities are reassigned (see Alg. 2). At any point in time the next query is
made to the entity with the earliest associated tentative next query time.
Note that since distinct buckets have distinct midpoints, and no bucket has
more than one associated entity, the current set of tentative next query times
contains no duplicates. In fact, for any two tentative query times associated
with entities in buckets $B$ and $B^{\prime}$, it must be that either $B$ and
$B^{\prime}$ are disjoint, or the smaller bucket is a sub-bucket of one half
of the larger bucket.

Recall from the invariant properties of bucket assignments in the basic
BucketScheme that if $e_{i}$ is assigned to bucket $B$, then
$\sigma_{i}(x,t)=\Theta(|T_{B}|)$ (i.e.
$1/\sigma_{i}(x,t)=\Theta(1/|T_{B}|)$), for $t\in T_{B}$. In the refined
BucketScheme this property is generalized to: (i) if $e_{i}$ is assigned to
bucket $B$, then there is a subset of entities $S_{B}$, including $e_{i}$,
such that $\sum_{e_{j}\in S_{B}}1/\sigma_{j}(x,t)=\Theta(1/|T_{B}|)$, for
$t\in T_{B}$, and (ii) if $T_{B}\cap T_{B^{\prime}}\neq\emptyset$ then
$S_{B}\cup S_{B^{\prime}}=\emptyset$. (It is straightforward to confirm that
this property is preserved by the reassignment of entities in the bucket
structure.)

Since the gap between successive queries contains half of the smaller of the
two buckets containing the two entities, it follows that every gap between
queries has an associated integral of
$\sum_{e_{j}\in\mathcal{E}}1/\sigma_{j}(x,t)$ that is $\Theta(1)$. It follows
from this that the stationary frequency demand is inversely proportional to
the instantaneous granularity at the time of every query.

Algorithm 2 Schedule*$(e_{j},B)$ $\triangleright$ used by the refined
BucketScheme

1:if bucket $B$ already contains an entity $e_{i}$ then $\triangleright$ $B$
contains at most one

2: Unassign $e_{i}$ from $B$

3: Schedule*$(e_{i},B_{\text{first}})$ $\triangleright$ $B_{\text{first}}$
spans the first half-interval of $B$

4: Schedule*$(e_{j},B_{\text{second}})$ $\triangleright$ $B_{\text{second}}$
spans the second half-interval of $B$

5:else

6: Assign $e_{j}$ to bucket $B$ with query time at the midpoint of $B$.

We summarize with:

######  Lemma 5.7.

Over any time interval $T$ in which the refined BucketScheme$[x]$ makes
$3|\mathcal{E}|$ queries, $\phi_{\mathcal{E},x}(T)=\Omega(|\mathcal{E}|)$.
Furthermore, at any time the query granularity is inversely proportional to
the stationary query demand.

Combining Lemma 5.7 and Corollary 2, we reach our main result:

######  Theorem 5.8.

The refined BucketScheme$[(1+\beta)x]$ maintains uncertainty degree (and hence
uncertainty ply) at most $(1+\beta)x$ and, over all sufficiently large time
intervals $T$, is competitive, in terms of total queries over $T$ or some
small shift $\overrightarrow{T}$ of $T$, with any query scheme that maintains
uncertainty ply at most $x$ over $T\cup\overrightarrow{T}$. The competitive
factor is (i) $O(x)$, when $\beta=0$, and (ii) $O(\frac{1+\beta}{\beta})$,
when $\beta>0$. Furthermore, at all times it uses query granularity that is
inversely proportional to the stationary frequency demand.

Appendix B describes a collection of mobile entities for which every query
scheme that maintains uncertainty ply at most $x$ at all times in a specified
time interval needs to use a query total that is at most a factor
$\frac{(1+2\beta)x+1}{2\beta x+3}$ smaller (and hence minimum query
granularity that is at most a factor $\frac{2\beta x+3}{(1+2\beta)x+1}$
larger) over the full interval than that used by the best query scheme for
achieving uncertainty degree at most $(1+\beta)x$ at all times in the same
interval. It follows that the competitive factor on total queries realized by
the refined BucketScheme, for maintaining uncertainty degree at most
$(1+\beta)x$ (or for maintaining uncertainty ply at most $(1+\beta)x$ by
maintaining uncertainty degree at most $(1+\beta)x$) cannot be improved by
more than a constant factor in general.

##  6 Discussion

###  6.1 Motivating applications revisited

We return briefly to the motivating applications mentioned in the
introduction. For the channel assignment application, observe that when our
scheme queries a transmission source $e_{i}$ (with associated transmission
range), it schedules the next query of $e_{i}$ knowing the set $E$ of
entities, other than $e_{i}$ itself, whose transmission ranges may potentially
conflict with that of $e_{i}$ from now until that query. Thus, choosing a
transmission channel for $e_{i}$ that differs from the transmission channels
assigned to entities in $E$ avoids transmission interference. This requires at
most $|E|+1$ channels, which if the scheme maintains uncertainty degree at
most $x$, is at most $x$. Note that channel assignments are updated _locally_
, i.e., only the assignment of the just-queried entity changes. Our scheme
guarantees uncertainty degree $(1+\beta)x$ using a query frequency that is (up
to a constant factor) optimally competitive with that required of any scheme
to maintain uncertainty ply (which bounds from below the number of
transmission channels used required to avoid potential transmission
interference) at most $x$.

Our assumption of disjoint entities (i.e. transmission ranges) is easily
relaxed to permit intersections up to some constant fraction of the
transmission area, changing all of our competitive bounds by at most a
constant.

For the collision avoidance application recall that by maintaining uncertainty
degree at most $x$, we maintain (using optimal query frequency) for each
entity $e_{i}$ a certificate identifying the, at most $x-1$, other entities
that could potentially collide with $e_{i}$ (those warranting more careful
local monitoring). Here too it is straightforward to make our results even
more directly applicable by strengthening the notion of encroachment to hold
when uncertainty regions have a separation less than some specified threshold.

###  6.2 Other Generalizations of our Model or Analysis

Several other modifications to our model are possible, making our query
optimization framework even more broadly applicable. Several of these are
mentioned below; details will be developed in an expanded version of this
paper.

####  6.2.1 Exploiting uniformity of entity distributions

As previously mentioned, our competitive bounds can be further strengthened by
making assumptions about the _uniformity_ of entity distributions. Define
$\mu_{\mathcal{E},x}=\frac{2^{1/d}\sum_{e_{i}\in\mathcal{E}}\frac{1}{r_{i}(2x)}}{\sum_{e_{i}\in\mathcal{E}}\frac{1}{r_{i}(x)}}$.
The expression $\mu_{\mathcal{E},x}$ can be viewed as a measure of the
$x$-uniformity of the distribution of entities in $\mathcal{E}$ at one fixed
moment in time: a completely uniform distribution would have
$\mu_{\mathcal{E},x}\approx 1$ and a large collection of isolated $x$-clusters
could have $\mu_{\mathcal{E},x}$ arbitrarily small. The uniformity-sensitivity
of our query schemes is expressed in terms of $\mu_{\mathcal{E},x}$. More
generally, define

$\mu_{\mathcal{E},x}(T)=\frac{2^{1/d}\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}{t}}{r_{i}(2x,t)}}{\sum_{e_{i}\in\mathcal{E}}\int_{T}\frac{\mathop{}\\!\mathrm{d}{t}}{r_{i}(x,t)}}$

as a measure of uniformity of the entity configurations over time interval
$T$.

Revisiting the proof of Theorem 4.4, we see that the ${\rm FWRR}[x]$ query
scheme uses a total number of queries over any time interval $T$ that is
competitive with any scheme that maintains uncertainty configurations with
uncertainty ply at most $x$ over $T$, and the competitive factor is
$O(\frac{1}{\mu_{\mathcal{E},x}})$, provided $|T|\phi_{\mathcal{E},2x}\geq
2|\mathcal{E}|$. This follows because

$\phi_{\mathcal{E},2x}\geq\sum_{e_{i}\in\mathcal{E}}\frac{1}{r_{i}(2x)}=\frac{\mu_{\mathcal{E},x}}{2^{1/d}}\sum_{e_{i}\in\mathcal{E}}\frac{1}{r_{i}(x)}\geq\frac{\mu_{\mathcal{E},x}\lambda_{d,x}}{2^{1/d}}\phi_{\mathcal{E},x}.$

Similarly, by revisiting the proof of Theorem 5.8, we see that, for all
sufficiently large time intervals $T$, the refined BucketScheme$[x]$ uses a of
total number of queries over $T$, or some small shift $\overrightarrow{T}$ of
$T$, that is competitive with any query scheme that maintains uncertainty ply
at most $x$ over $T\cup\overrightarrow{T}$. The competitive factor is
$O(\frac{1}{\mu_{\mathcal{E},x}(T)})$, when the entity set $\mathcal{E}$ has
$x$-uniformity $\mu_{\mathcal{E},x}(T)$ over $T$. In this case we make use of
the fact that
$\phi_{\mathcal{E},2x}(T)\geq\frac{\mu_{\mathcal{E},x}(T)\lambda_{d,x}}{2^{1/d}}\phi_{\mathcal{E},x}(T)$.

####  6.2.2 Relaxing the assumption of uniform entity extent

We have assumed that all entities are $d$-dimensional balls with the same
extent (radius) $\rho$. Relaxing this assumption impacts the relationship
between the $x$-radius and $x$-separation of entities, captured in Equation 2.
Nevertheless, if entity extents differ by at most a constant factor, it is
straightforward to modify the constants $\lambda_{d,x}$ and $\hat{x}_{d}$, so
that all of our results continue to hold.

####  6.2.3 Relaxing the assumption of uniform entity speed

Similarly, the reader will not be surprised by the fact our results are
essentially unchanged if our assumption that all entities have the same (unit)
bound on their maximum speed is relaxed to allow speed bounds that differ by
at most a constant factor. Allowing non-constant factor differences in speed
bounds creates some additional challenges and some helpful new insights into
the nature of our results. Surprisingly perhaps, our query schemes can be
generalized in a rather straightforward way to accommodate such a change.
However, our competitiveness results for maintaining bounded uncertainty
degree only hold with respect to other (even clairvoyant) schemes with the
same objective. This is unavoidable since, when entities have arbitrarily
different maximum speeds, uncertainty configurations with maximum ply $x$
could have arbitrarily large degree.

####  6.2.4 Decentralization of our query schemes

Our query model implicitly assumes that query decisions are centralized;
location queries are issued from a single source. However, it is not hard to
see that our query schemes, assuming suitable initial synchronization, could
be fully decentralized, with location queries to entity $e_{i}$ replaced by
location broadcasts from entity $e_{i}$. This is particularly interesting in
the situation where entity speed bounds could be arbitrarily different, since
an entity can decide when to make its next location broadcast without knowing
the speed bounds associated with other entities.

## References

  * [1] Shoshana Anily, Celia A. Glass, and Refael Hassin.  The scheduling of maintenance service.  Discrete Applied Mathematics, 82:27–42, 1998.
  * [2] Julien Basch, Leonidas J. Guibas, and John Hershberger.  Data structures for mobile data.  Journal of algorithms, 31(1):1–28, 1999.
  * [3] Daniel Busto, William Evans, and David Kirkpatrick.  Minimizing interference potential among moving entities.  In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2400–2418, 2019.
  * [4] John Horton Conway and Neil James Alexander Sloane.  Sphere packings, lattices and groups, volume 290.  Springer Science & Business Media, 1999.
  * [5] Mark de Berg, Marcel Roeloffzen, and Bettina Speckmann.  Kinetic compressed quadtrees in the black-box model with applications to collision detection for low-density scenes.  In European Symposium on Algorithms, pages 383–394. Springer, 2012\.
  * [6] Mark de Berg, Marcel Roeloffzen, and Bettina Speckmann.  Kinetic convex hulls, delaunay triangulations and connectivity structures in the black-box model.  Journal of Computational Geometry, 3(1):222–249, 2012.
  * [7] Mark de Berg, Marcel Roeloffzen, and Bettina Speckmann.  Kinetic 2-centers in the black-box model.  In Symposium on Computational Geometry, pages 145–154, 2013.
  * [8] Thomas Erlebach and Michael Hoffmann.  Query-competitive algorithms for computing with uncertainty.  Bull. Eur. Assoc. Theor. Comput. Sci., 2(116), 2015.
  * [9] William Evans, David Kirkpatrick, Maarten Löffler, and Frank Staals.  Competitive query strategies for minimising the ply of the potential locations of moving points.  In Proceedings of the Twenty-ninth Annual Symposium on Computational Geometry, SoCG ’13, pages 155–164, New York, NY, USA, 2013. ACM.  URL: http://doi.acm.org/10.1145/2462356.2462395, doi:10.1145/2462356.2462395.
  * [10] William Evans, David Kirkpatrick, Maarten Löffler, and Frank Staals.  Query strategies for minimizing the ply of the potential locations of entities moving with different speeds.  In Abstr. 30th European Workshop on Computational Geometry (EuroCG), 2014.
  * [11] William Evans, David Kirkpatrick, Maarten Löffler, and Frank Staals.  Minimizing co-location potential of moving entities.  SIAM Journal on Computing, 45(5):1870–1893, 2016.
  * [12] P. C. Fishburn and J. C. Lagarias.  Pinwheel scheduling: Achievable densities.  Algorithmica, 34(1):14–38, 2002.
  * [13] L. J. Guibas.  Kinetic data structures — a state of the art report.  In P. K. Agarwal, L. E. Kavraki, and M. Mason, editors, Proc. Workshop Algorithmic Found. Robot., pages 191–209. A. K. Peters, Wellesley, MA, 1998.
  * [14] Leonidas J. Guibas and Marcel Roeloffzen.  Modeling motion.  In Csaba D. Toth, Joseph O’Rourke, and Jacob E. Goodman, editors, Handbook of discrete and computational geometry, chapter 53, pages 1401–1420. CRC press, 2017.
  * [15] R. Holte, A. Mok, L. Rosier, I. Tulchinsky, and D. Varvel.  The pinwheel: a real-time scheduling problem.  In Proceedings of the Twenty-Second Annual Hawaii International Conference on System Sciences. Volume II: Software Track, pages 693–702, 1989\.  doi:10.1109/HICSS.1989.48075.
  * [16] Simon Kahan.  A model for data in motion.  In Proceedings of the Twenty-third Annual ACM Symposium on Theory of Computing, STOC ’91, pages 265–277, 1991.
  * [17] Simon Kahan.  Real-Time Processing of Moving Data.  PhD thesis, University of Washington, Sep. 1991.
  * [18] Maarten Löffler and Jack Snoeyink.  Delaunay triangulation of imprecise points in linear time after preprocessing.  Computational geometry : theory and applications, 43(3):234–242, 2010.

##  Appendix A  Limitations on Competitiveness: Stationary Entities

Fixed-time vs continuous-time optimization. Consider a collection of $n/2$
well-separated pairs, where the $i$-th pair has separation $4i-1$. Uncertainty
ply (and degree) can be kept at one at a deadline $n$ time units from the
start, by a scheme that queries entities with granularity one in decreasing
order of their separation. On the other hand to maintain degree/ply one
continuously, the $i$-th entity pair must be queried at least once every
$4i-1$ steps, so over any time interval of length $n$, $\Omega(n\ln n)$
queries are required.

Maintaining ply vs degree. The example involves two clusters $A$ and $B$ of
$(x+\beta x+1)/2$ point entities separated by distance $4(1+\beta x)$. To
maintain uncertainty ply at most $x$ it suffices to query $\beta x+1$ entities
in both clusters once every $2(1+\beta x)$ steps, which can be achieved with
query frequency one. Since the uncertainty regions associated with queried
points in cluster $A$ never intersect the uncertainty regions associated with
queried points in cluster $B$, the largest ply possible involves points in one
cluster (say $A$) together with unqueried points in the other cluster ($B$),
for a total of $x$.

On the other hand, to maintain degree at most $x+\beta x$ no uncertainty
region can be allowed to have radius $4(1+\beta x)$. Thus all $(1+\beta)x+1$
entities need to be queried with frequency at least $1/(4(1+\beta x))$, giving
a total query demand of $(1+\beta)x+1$ over any time interval of length
$4(1+\beta x)$.

##  Appendix B  Limitations on Competitiveness: Moving Entities

The fixed target time case. Imagine a configuration involving two collections
$A$ and $B$ each with $(x+1)/2+\beta x$ point entities located in
$\mathbb{R}^{1}$, on opposite sides of a point $O$. At time $0$ all of the
entities are at distance $x+4\beta x+4$ from $O$, but have unbounded
uncertainty regions. All entities begin by moving towards $O$ at unit speed,
but at time $2\beta x+3$ a subset of $\beta x+1$ entities in each of $A$ and
$B$ (the special entities) change direction and move away from $O$ at unit
speed, while the others carry on until the target time $x+4\beta x+4$ when
they simultaneously reach $O$ and stop.

To avoid uncertainty degree greater than $(1+\beta)x$ at a target time a
clairvoyant scheme needs only to (i) query all entities (in arbitrary order)
up to time $x+2\beta x+1$, and then (ii) query just the special entities (in
arbitrary order) in the next $2\beta x+2$ time prior to the target, using
query granularity $1$, since doing so will leave the uncertainty regions of
the points in $A$ disjoint from the special points in $B$, and vice versa.

On the other hand, to avoid ply $x$ at the target time any scheme must query
all special entities in both $A$ and $B$ in the last $2\beta x+3$ time before
the target, which in the absence of knowledge about which entities are special
requires all entities in both $A$ and $B$ to be queried in the worst case,
requiring query granularity that is at most $\frac{2\beta x+3}{x+1+2\beta x}$.

Thus for this instance every scheme that achieves congestion ply at most $x$
at the target time needs to use minimum query granularity, over a time
interval of length $2\beta x+3$ preceding the target, that is at most a factor
$\frac{2\beta x+3}{(1+2\beta)x+1}$ larger than that used by the best query
scheme for achieving congestion degree at most $(1+\beta)x$ at the target
time.

The continuous case. A very similar construction allows us to conclude
essentially the same result in the continuous case: every scheme that
maintains uncertainty ply at most $x$ at all times in a specified interval
needs to use a query total that is at most a factor
$\frac{(1+2\beta)x+1}{2\beta x+3}$ smaller (and hence minimum query
granularity that is at most a factor $\frac{2\beta x+3}{(1+2\beta)x+1}$
larger) over the full interval than that used by the best query scheme for
achieving congestion degree at most $(1+\beta)x$ at all times in the same
interval.

It remains the case that to avoid ply $x$ just at the target time any scheme
must query all special entities in both $A$ and $B$ before the target time,
requiring query granularity at most $\frac{2\beta x+3}{x+1+2\beta x}$.
Furthermore, it should be clear that, even if there are no queries prior to
what we called the target time, the fixed target time construction cannot lead
to uncertainty degree more than $(x+1)/2+\beta x$ prior to that time. So it
remains to show that a clairvoyant scheme can continue to maintain degree at
most $(1+\beta)x$ thereafter using query granularity $1$ (i.e. the query
scheme has not simply deferred a situation in which smaller query granularity
is needed to maintain degree $(1+\beta)x$). To see this, note that every time
one of the special entities is queried it is seen to have distance exactly
$2\beta x+3$ from the uncertainty regions associated with non-special entities
on the other side of $O$, up to the time the non-special entities reach $O$,
and at least $2\beta x+3$ thereafter, even if non-special entities are never
queried. Thus it certainly suffices to query all $2\beta x+2$ of the special
entities at least once every $2\beta x+2$ time steps to guarantee that their
associated uncertainty region remains disjoint from the uncertainty regions of
all non-special entities on the other side of $O$. This can clearly be done
using query granularity $1$.

There might be some concern that (i) the construction assumes $n$, the total
number of entities, is $x+1+2\beta x$, and (ii) the competitive gap
demonstrated by this example is only transitory, since after the target time a
non-clairvoyant scheme could also maintain low congestion using granularity
$1$. However, it is straightforward to modify the construction, by well-
separated replication, to make $n$ arbitrary large relative to $x$.
Furthermore, by having the non-special entities retreat from $O$ at unit speed
after the target time, one can essentially recreate the initial configuration
and thereafter reproduce the high competitive gap periodically.