Evolving Distributions Under Local Motion

Acharya, Aditya; Mount, David M.

doi:10.4230/LIPIcs.WADS.2025.4

Evolving Distributions Under Local Motion

Aditya Acharya

Department of Computer Science, University of Maryland, College Park, MD, USA David M. Mount

Department of Computer Science and Institute for Advanced Computer Studies, University of Maryland, College Park, MD, USA

Abstract

Geometric data sets that arise in modern applications are often very large and change dynamically over time. A popular framework for dealing with such data sets is the evolving data framework, where a discrete structure continuously varies over time due to the unseen actions of an evolver, which makes small changes to the data. An algorithm probes the current state through an oracle, and the objective is to maintain a hypothesis of the data set’s current state that is close to its actual state at all times. In this paper, we apply this framework to maintaining a set of $n$ point objects in motion in $d$ -dimensional Euclidean space. To model the uncertainty in the object locations, both the ground truth and hypothesis are based on spatial probability distributions, and the distance between them is measured by the Kullback-Leibler divergence (relative entropy). We introduce a simple and intuitive motion model in which, with each time step, the distance that any object can move is a fraction of the distance to its nearest neighbor. We present an algorithm that, in steady state, guarantees a distance of $O(n)$ between the true and hypothesized placements. We also show that for any algorithm in this model, there is an evolver that can generate a distance of $\Omega(n)$ , implying that our algorithm is asymptotically optimal.

Keywords and phrases:

Evolving data, tracking, imprecise points, local-motion model, online algorithms

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Computational geometry

Related Version:

Full Version: https://arxiv.org/pdf/2409.11779

Acknowledgements:

The authors would like to thank Michael Goodrich for suggesting the question of how to model multidimensional evolving point sets.

DOI:

10.4230/LIPIcs.WADS.2025.4

Event:

19th International Symposium on Algorithms and Data Structures (WADS 2025)

Editors:

Pat Morin and Eunjin Oh

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Many modern computational applications are characterized by two qualities: data sets are massive and vary over time. A fundamental question is how to maintain some combinatorial structure that is a function of such a data set. The combination of size and dynamics makes maintaining such a structure challenging. Given the large data sizes, single-shot algorithms may be too slow, and common dynamic algorithms, which support explicit requests for insertions and deletions, may not be applicable because structural changes are unseen by the algorithm.

Anagnostopoulos, Kumar, Mahdian, Upfal, and Vandin introduced a model for handling such data sets, called the evolving data framework [2]. In this framework, the structure varies repeatedly over time through the unseen actions of an evolver, which makes small, stochastic changes to the data set. The algorithm can probe the current state locally using an oracle. With the aid of this oracle, the algorithm maintains a hypothesis of the current state of the structure that is as close as possible to its actual state at all times. The similarity between the hypothesis and the current state is measured through some distance function. The algorithm’s objective is to achieve, in the steady state, a small distance between the hypothesis and the actual state. This framework has been applied to a variety of problems [1, 6, 21, 17, 36].

Consider, for example, sorting. The data consists of a set of objects over some total order. The evolver repeatedly selects a random pair of adjacent objects and swaps them. The oracle is given two objects and returns their relative order. The objective of the algorithm is to maintain an order that is as close to the current state as possible, where the distance is measured in terms of the Kendall tau distance, that is, the number of pairwise order inversions [22]. It has been shown that a Kendall tau distance of $O(n)$ is achievable, and this is optimal [6, 5]. It is noteworthy that the optimal algorithm in the evolving framework is based on a simple quadratic-time sequential algorithm, and not $O(n\log n)$ -time algorithms, as one might expect. The sorting problem has been generalized to tracking labels on a tree in [1], laying the foundations for a geometric framework for evolving data.

This paper focuses on the question of how to maintain a set of points whose positions evolve continuously in real $d$ -dimensional space, $\mathbb{R}^{d}$ . In motion tracking applications, object movement is recorded through various technologies, including GPS-enabled mobile devices [31], RFID tags [28], and camera-based sensing [35]. Examples include the movement and migration of animals on land and in oceans, traffic and transport, defense and surveillance, and analysis of human behavior (see, e.g., [13, 24]).

Imprecision and uncertainty are unavoidable problems that arise in evolving systems. Due to sensor latency, the exact location of any object cannot be known with certainty. In the best case, any algorithm can maintain only an approximation to the current state. In order to bound the degree of uncertainty, it is necessary to impose restrictions on object motion. In traditional applications of the evolving data framework, the evolver acts randomly. This is not a reasonable assumption in practice, where moving objects are subject to physical laws or may have a sense of agency [15, 32, 34]. Much work has focused on realistic models of motion, but these can be difficult to analyze theoretically. A widely used model assumes that objects have a maximum speed limit, and as time passes, an object can be inferred to lie within a ball whose radius grows linearly over time based on this speed limit [9, 12, 20]. However, in practice, the speed that any object can move depends on the congestion within its local environment.

In multidimensional space, there is no intrinsic total order, and it is less clear what it means to accurately track imprecise moving objects. Given the inherent uncertainty, we model the location of each object in terms of a spatial probability distribution. The distance between the actual state of the system and our hypothesis is naturally defined as the relative entropy (Kullback-Leibler divergence) between these two distributions. The Kullback-Leibler (KL) divergence is a fundamental measure in statistics that represents the distance between two probability distributions [23]. It has numerous applications in statistical inference, coding theory, machine learning, among others [10]. In our case, it serves two intuitive purposes. First, it measures how different the truth is from our hypothesis. Second, it can be used to quantify the additional information required to encode the actual location of each object, based on our hypothesis [10].

For the evolution of our data, we adopt a locality-sensitive stochastic motion model. We assume that with each time step, the motion of an object is constrained by its immediate environment, which we call the local-motion model. In this model, the distance that any object can move in a single time step is a fixed fraction of the distance to its nearest neighbor. The support of this object’s probability distribution is a region of size proportional to the nearest-neighbor distance. This model has the advantage that it does not impose arbitrary speed limits on the movement of objects, it is invariant under transformations that preserve relative distances (e.g., translation, rotation, and uniform scaling), and it satisfies the observed phenomenon that objects in dense environments have less personal space [19, 16], and exhibit slower movement than those in sparse environments [29, 4].

To control the communication complexity in determining object locations, we do not require that the oracle returns the exact object positions. Instead, we assume access to an oracle that is given a Euclidean ball and the index $i$ of an object. It returns a pair of bits indicating whether the $i$ -th object lies within this ball and (if so) whether there is any other object of the set within this ball. Since every object’s location is subject to uncertainty, the same query on the oracle might result in different outcomes at different times, and our algorithm is robust to such variations.

In our framework, the evolver and the algorithm operate asynchronously and in parallel. With each time step, the evolver selects an arbitrary object of the set and moves it in accordance with the local-motion model. (This need not be random and may even be adversarial.) This information is hidden from our algorithm. The algorithm selects an object and invokes the oracle on this object. Based on the oracle’s response, the algorithm updates the current hypothesized distribution for this point. Thus, the evolver and algorithm are involved in a pursuit game, with the evolver incrementally changing object distributions (possibly in an adversarial manner) and the algorithm updating its hypothesized distributions. The algorithm’s goal is to minimize the relative entropy between these distributions at all times. Our computational model and a formal statement of our results are presented in Section 2.

2 Problem Formulation and Results

Objects

The objects that populate our system can be thought of as imprecise points [8, 14, 25] that are drawn independently from probability distributions that depend on the proximity to other objects. More formally, at any fixed time step, let $Q=\{\mathbf{q}_{1},\ldots,\mathbf{q}_{n}\}\subset\mathbb{R}^{d}$ denote a point set of size $n$ in $d$ -dimensional Euclidean space, and let $[n]$ denote the index set $\{1,\ldots,n\}$ . For each $\mathbf{q}_{i}\in Q$ , let $N_{i}$ denote the distance to its nearest neighbor in $Q\setminus\{\mathbf{q}_{i}\}$ . Given $\mathbf{x}\in\mathbb{R}^{d}$ and nonnegative real $r$ , let $\mathcal{B}(\mathbf{x},r)$ denote the closed Euclidean ball of radius $r$ centered at $\mathbf{x}$ , and let $\mathrm{U}(\mathcal{B}(\mathbf{x},r))$ denote the uniform probability distribution over this ball. Given a real $\beta$ , where $0<\beta<1$ , define the $\beta$ -local feature region of $\mathbf{q}_{i}$ to be $\mathcal{B}(\mathbf{q}_{i},\beta N_{i})$ . Let $P_{i}=P_{i}(\beta)$ denote the uniform¹¹1Our choice of using a uniform probability distribution is not critical to our approach. In the full version of the paper we show that our results apply to a much broader class of distributions. probability distribution, $\mathrm{U}\left(\mathcal{B}(\mathbf{q}_{i},\beta N_{i})\right)$ , and let $\mathcal{P}=\{P_{1},\ldots,P_{n}\}$ denote this set of distributions. We refer to $\mathcal{P}$ as the truth or ground truth, as it represents the true state of the system, subject to the given imprecision. Together, $Q$ and $\beta$ define a set $n$ independent random variables $\{X_{1},\ldots,X_{n}\}$ , with $X_{i}$ distributed as $P_{i}$ (see Figure 1(a)).

(a) Illustration of the objects, and the notations used. The evolver’s action

\varepsilon

is shown in red.

(b) Objects that were affected by

\varepsilon

are shown in pink. Tiled regions show the previous state.

Figure 1: The model and an action by the evolver. Shaded regions represent objects.

The Local-Motion Model

As mentioned in the introduction, there are many ways to model the realistic motion of a collection of objects in an environment. A natural requirement is that each object’s motion is affected by the presence of nearby objects. Although there are many ways to incorporate this information (see, e.g., [29]), we have chosen a very simple model, where velocities are influenced by the distance to the nearest neighbor.

We think of the objects of our system as moving continuously over time, and our algorithm queries their state at regular discrete time steps. From the algorithm’s perspective, objects move, or “evolve,” over time in the following manner. Given a parameter $\alpha$ , where $0<\alpha<1$ , at each time step, an entity called evolver selects an object $i\in[n]$ and moves $\mathbf{q}_{i}$ by a distance of at most $\alpha N_{i}$ in any direction of its choosing (see Figure 1). While the value of $\alpha$ is known, the action of the evolver, including the choice of the object and the movement, is hidden from the algorithm. Throughout, we assume that the evolver is a strong adversary, which means that it has access to our algorithm and the input set [7].

For a nonnegative integer time step $t$ , let $Q^{(t)}$ and $\mathcal{P}^{(t)}$ denote the underlying centers and distributions, respectively, at this time. To simplify notation, we omit the superscript when talking about the current time. We assume that there exists a bounding region in the form of a Euclidean ball $\mathcal{B}_{0}$ centered at the origin. At all times, the points $Q^{(t)}$ are restricted to lie within $\mathcal{B}_{0}$ . The algorithm has knowledge of this ball. Define the system’s initial aspect ratio to be $\Lambda_{0}=(\operatorname{radius}(\mathcal{B}_{0}))/(\min_{i\in[n]}N_{i}^{(0)})$ . Given any positive constant $c$ , let $c\mathcal{B}_{0}$ denote a factor- $c$ expansion of this ball about the origin.

Oracle

Consider the state of the system at any fixed time $t$ . Knowledge about the current state of the system is provided by an entity $\mathcal{O}$ , called the oracle. It is given a Euclidean ball $\mathcal{B}(\mathbf{x},r)$ and an object index $i\in[n]$ . Recall that for each $i\in[n]$ , $X_{i}$ denotes a random variable distributed as $P_{i}$ . The oracle is a function $\mathcal{O}:[n]\times\mathbb{R}^{d}\times\mathbb{R}^{+}\rightarrow\{Y,N\}% \times\{+,-\}$ , where $\mathcal{O}(i,\mathbf{x},r)$ returns:

$\blacksquare$

“ $Y$ ” or “ $N$ ” depending on whether $X_{i}\in\mathcal{B}(\mathbf{x},r)$ and
$\blacksquare$

“ $+$ ” or “ $-$ ” depending on whether there exists $j\neq i$ , such that $X_{j}\in\mathcal{B}(\mathbf{x},r)$

The first element of the pair is used to estimate the location of the object $i$ , and the second is used to estimate the distance to its nearest neighbor. Because $X_{i}$ and $X_{j}$ are random variables, so is $\mathcal{O}(i,\mathbf{x},r)$ . Consistent with previous applications of the evolving data framework (see, e.g., [3]), we intentionally made the oracle as weak as possible, implying that our algorithm can be used with stronger oracles.

Hypotheses and Distance

The algorithm maintains a hypothesis of the current object locations, which is defined to be a set $\mathcal{H}=\{H_{1},\ldots,H_{n}\}$ of spatial probability distributions in $\mathbb{R}^{d}$ . The distance between the truth $\mathcal{P}$ and the current hypothesis $\mathcal{H}$ , denoted $\mathcal{D}(\mathcal{P},\mathcal{H})$ , is defined as the sum of $n$ Kullback-Leibler divergences from the hypothesized distributions to the true ones. For $i\in[n]$ , let

D_{i}\leavevmode\nobreak\ =\leavevmode\nobreak\ D_{\text{KL}}(P_{i}\parallel H% _{i})\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathbf{x}\in\mathcal{B}% _{i}}P_{i}(\mathbf{x})\log\frac{P_{i}(\mathbf{x})}{H_{i}(\mathbf{x})}\mu(d% \mathbf{x}),

where $\mu(\cdot)$ denotes the measure over $\mathcal{B}_{i}=\mathcal{B}(\mathbf{q}_{i},\beta N_{i})$ and define

\mathcal{D}(\mathcal{P},\mathcal{H})\leavevmode\nobreak\ =\leavevmode\nobreak% \ \sum_{i=1}^{n}D_{i}\leavevmode\nobreak\ =\leavevmode\nobreak\ \sum_{i=1}^{n}% D_{\text{KL}}(P_{i}\parallel H_{i}).

(1)

As a baseline for comparisons, we introduce a naïve hypothesis, denoted $\mathcal{H}^{*}$ , which assumes no information about the locations of the objects, other than the fact that they lie within the bounding region. Recall that $\mathcal{B}_{0}$ denotes this bounding region and $3\mathcal{B}_{0}$ denotes a factor- $3$ expansion about its center. Since all the points of $Q$ lie within $\mathcal{B}_{0}$ and $0<\beta<1$ , $3\mathcal{B}_{0}$ is guaranteed to contain all the $\beta$ -local feature regions. For all $i\in[n]$ , let $H_{i}^{*}$ be the uniform distribution over $3\mathcal{B}_{0}$ , and let $\mathcal{H}^{*}=\{H_{1}^{*},\ldots,H_{n}^{*}\}$ . Regardless of the initial truth, the initial distance of the $i$ th object satisfies the following bound.

	$\displaystyle D_{i}^{}\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{% \mathbf{x}\in\mathcal{B}_{i}}P_{i}(\mathbf{x})\log\frac{P_{i}(\mathbf{x})}{H_{% i}^{}(\mathbf{x})}\mu(d\mathbf{x})$	$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathbf{x}\in% \mathcal{B}_{i}}P_{i}(\mathbf{x})\log\frac{1/(\beta N_{i})^{d}}{1/(3\cdot% \operatorname{radius}(\mathcal{B}_{0}))^{d}}\mu(d\mathbf{x})$
		$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \log\left(\frac{3\cdot% \operatorname{radius}(\mathcal{B}_{0})}{\beta N_{i}}\right)^{d}\int_{\mathbf{x% }\in\mathcal{B}_{i}}P_{i}(\mathbf{x})\mu(d\mathbf{x})$
		$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ d\left(\log\Lambda_% {0}+\log\frac{3}{\beta}\right).$

Let $\mathcal{D}=\sum_{i\in[n]}D_{i}^{*}$ . Under our assumption that $d$ and $\beta$ are constants, we have $\mathcal{D}^{*}\in\Theta(n\log\Lambda_{0})$ . The initial aspect ratio, $\Lambda_{0}$ , depends on the initial configuration of the points of $Q$ , and can be arbitrarily high. In the best case, when the points are uniformly distributed in $\mathcal{B}_{0}$ , we have $\Lambda_{0}=\Omega(n^{1/d})$ and hence $\mathcal{D}\in\Omega(n\log n)$ . The objective of our algorithm is to maintain a significantly smaller bound on this distance.

The combination of evolver, oracle, and distance function constitute a model of evolving motion, which we henceforth call the $(\alpha,\beta)$ -local-motion model.

Class of Algorithms

We assume that the algorithm that maintains the hypothesis runs in discrete steps over time. With each step, it may query the oracle a constant number of times, perform a constant amount of work, and then update the current set of hypotheses. The number of oracle queries is independent of $n$ but can depend on dimension $d$ , local feature scale factor $\beta$ , and motion factor $\alpha$ . In our case, this work takes the form of updating the hypothesis for the object that was queried. In the purest form of the evolving data framework, the evolver and algorithm alternate [2]. Instead, similar to the generalized framework proposed in [1], we assume that there is a fixed speed-up factor, denoted $\sigma$ . When amortized over the entire run, the ratio of the number of steps taken by the algorithm and the evolver does not exceed $\sigma$ .

Objective and Results

The objective of the algorithm is as follows. Given any starting ground-truth configuration, after an initial “burn-in” period, the algorithm guarantees that the hypothesis is within a bounded distance of the truth subject to model assumptions and the given speed-up factor. Our main result is that there exists an algorithm with constant speed-up factor $\sigma$ that maintains a distance of $O(n)$ in steady state.

Theorem 1.

Consider a set of $n$ evolving objects in $\mathbb{R}^{d}$ under the $(\alpha,\beta)$ -local-motion model, for constants $\alpha$ and $\beta$ , where $0<\alpha,\beta<\frac{1}{3}$ . There exists an algorithm of constant speed-up $\sigma$ , and burn-in time $t_{0}\in O(n\log\Lambda_{0}\log\log\Lambda_{0})$ such that for all $t\geq t_{0}$ , this algorithm maintains a distance of $O(n)$ .

The algorithm and its analysis will be proved in Section 4. Given that no algorithm can guarantee an exact match between hypothesis and truth, it is natural to wonder how close this is to optimal. In Section 3, we will show that it is asymptotically optimal by showing that for any algorithm and any constant speed-up factor, there exists an evolver that can force a distance of $\Omega(n)$ in steady state.

Why the KL Divergence?

The principal challenge in generalizing the evolving framework from simple 1-dimensional applications like sorting to a multidimensional setting is the lack of an obvious distance measure that captures how close the hypothesis is to the current state. Our approach is motivated by an information-theoretic perspective. The KL divergence $D_{i}=D_{\text{KL}}(P_{i}\parallel H_{i})$ serves as a measure of how different the actual object distribution $P_{i}$ is from our hypothesis $H_{i}$ . (Note that the KL divergence is asymmetric, which is to be expected, given the asymmetric roles of the truth and our hypothesis.)

As an example of this information-theoretic approach, consider the following application in coding theory and space quantization [10]. The objective is to communicate the location of an imprecise point $X_{i}$ with any arbitrary resolution $\delta$ . From Shannon’s source coding theorem [26], the theoretical lower bound for the expected number of bits required for communication is given by the Shannon entropy [30]

b_{P_{i}}\leavevmode\nobreak\ =\leavevmode\nobreak\ \sum_{C_{\delta}\in B_{i}}% P_{i}(C_{\delta})\log\frac{1}{P_{i}(C_{\delta})},

where $C_{\delta}$ is a cell (a $d$ -dimensional box) of size $\delta$ in $\mathbb{R}^{d}$ , and $P(C)$ , by a slight abuse of notation, is the probability associated with a cell $C$ using the underlying probability distribution function $P$ . This is roughly achieved by a Huffman coding [18] of the space around $q_{i}$ , which intuitively assigns a number of bits proportional to the log of the inverse of the probability measure associated with an event, which in our case is $X_{i}$ lying within a cell $C_{\delta}$ of size $\delta$ .

Since the $P_{i}$ ’s are not available to us, we use a similar strategy of encoding the space using $H_{i}$ . Therefore, in expectation, we use roughly

b_{H_{i}}\leavevmode\nobreak\ =\leavevmode\nobreak\ \sum_{C_{\delta}\in B_{i}}% P_{i}(C_{\delta})\log\frac{1}{H_{i}(C_{\delta})}

bits. When $\delta$ is arbitrarily small, the difference $(b_{H_{i}}-b_{P_{i}})\sim D_{i}$ . Therefore, $\mathcal{D}(\mathcal{P},\mathcal{H})=\sum_{i\in[n]}D_{i}$ roughly represents the expected number of additional bits needed to represent the location of $X_{i}$ ’s individually using just $H_{i}$ ’s, compared to the absolute theoretical limit.

Paper Organization

The remainder of the paper is organized as follows. In the next section, we present Theorem 2, which provides a lower bound on the distance achievable by any algorithm in our model. In Section 4, we present the algorithm and analyze its steady-state performance. In Section 5, we discuss possible relaxations to the assumptions made in our model.

3 Lower Bound

In this section, we show that maintaining $\operatorname{\mathcal{D}(\mathcal{P},\mathcal{H})}\in O(n)$ is the best we can hope to achieve. This is established in the following theorem. Due to space limitations, the proof has been deferred to Section A.1.

Theorem 2.

For any algorithm $\mathcal{A}$ , there exists a starting configuration $Q^{(0)}$ and an evolver (with knowledge of $\mathcal{A}$ ) in the local-motion model such that, for any positive integer $t_{0}$ , there exists $t\geq t_{0}$ , such that $\mathcal{D}^{(t)}=\mathcal{D}(\mathcal{P}^{(t)},\mathcal{H}^{(t)})\in\Omega(n)$ .

The proof follows a similar structure to other lower-bound proofs in the evolving data framework [3, 6, 1]. Intuitively, over a period of time of length $c\kern 1.0ptn$ , for $c<1$ , the algorithm can inspect the locations of only a constant fraction of points. During this time, the evolver can move a sufficient number of uninspected points so that the overall distance increases by $\Omega(n)$ .

4 Algorithm

In this section, we present our algorithm and analyze its performance. We begin by defining our hypothesis. For every index $i$ , we define two parameters: $h_{i}\in\mathbb{R}$ , and $\mathbf{k}_{i}=(k_{i,1},\ldots k_{i,d})\in\mathbb{R}^{d}$ . For $\mathbf{x}=(x_{1},\ldots x_{d})\in\mathbb{R}^{d}$ we set the hypothesis probability density for the $i$ th point to be the $d$ -fold product of independent Cauchy distributions, one per coordinate, with center at $\mathbf{k}_{i}$ and scaling parameter $h_{i}$ [33]. That is,

H_{i}(\mathbf{x})\leavevmode\nobreak\ =\leavevmode\nobreak\ f_{h_{i},\mathbf{k% }_{i}}(\mathbf{x})\leavevmode\nobreak\ =\leavevmode\nobreak\ \frac{1}{\pi^{d}h% _{i}^{d}}\prod_{j=1}^{d}\left({1+\frac{\left(x_{j}-{k}_{i,j}\right)^{2}}{h_{i}% ^{2}}}\right)^{-1}

(2: Hypothesis Def.)

(Note that this differs from the standard multivariate Cauchy [33].) If we let $f_{1,\mathbf{0}}(\mathbf{x})$ denote the probability density function for the standard $d$ -fold product of Cauchy distributions (centered at the origin unit scale), we can express this equivalently as

f_{h_{i},\mathbf{k}_{i}}(\mathbf{x})\leavevmode\nobreak\ =\leavevmode\nobreak% \ \frac{1}{h^{d}_{i}}f_{1,\mathbf{0}}\left(\frac{\mathbf{x}-\mathbf{k}_{i}}{h_% {i}}\right),\quad\text{where}\quad f_{1,\mathbf{0}}(\mathbf{x})\leavevmode% \nobreak\ =\leavevmode\nobreak\ \frac{1}{\pi^{d}}\prod_{j=1}^{d}\left(1+x_{j}^% {2}\right)^{-1}.

It will be convenient to define the hypothesis ball $\mathcal{B}^{H}_{i}=\mathcal{B}(\mathbf{k}_{i},h_{i})$ , which we use to illustrate $H_{i}$ . Note that, unlike our truth probabilities $P_{i}$ , our hypothesis distributions have unbounded support. Our algorithm modifies the parameters $\mathbf{k}_{i}$ and $h_{i}$ in response to information received from the oracle.

4.1 Potential Function

Due to the subtleties of tracking the Kullback-Leibler divergence, we introduce a potential function $\Phi$ to aid in the analysis. For each object index $i\in[n]$ , we define an individual potential function $\Phi_{i}$ , which bounds the distance $D_{i}$ to within a constant. The total potential $\Phi$ will be the sum of these functions.

Let $s_{i}=\|\mathbf{q}_{i}-\mathbf{k}_{i}\|$ denote the Euclidean distance between the center of the actual distribution and the center of the hypothesis ball. Let $l_{i}=\beta N_{i}$ denote the radius of the local feature of $\mathbf{q}_{i}$ . Recall that $h_{i}$ is the radius of the hypothesis ball (see Figure 2). We define the individual and system potentials to be

\Phi_{i}\leavevmode\nobreak\ =\leavevmode\nobreak\ \Phi(P_{i},H_{i})% \leavevmode\nobreak\ =\leavevmode\nobreak\ \log\left(\frac{\max(s_{i},l_{i},h_% {i})}{\sqrt{l_{i}h_{i}}}\right)\quad\text{and}\quad\Phi\leavevmode\nobreak\ =% \leavevmode\nobreak\ \Phi(\mathcal{P},\mathcal{H})\leavevmode\nobreak\ =% \leavevmode\nobreak\ \sum_{i\in[n]}\Phi_{i}

(3)

The following lemma shows that, up to additive and scalar constants that depend on the dimension, distances can be bounded above by this potential.

Figure 2: The definition of the individual potential

\Phi_{i}

.

Lemma 3.

There exists a constant $c_{d}$ (depending on dimension) such that for any $i\in[n]$ , $D_{i}\leq c_{d}(1+\Phi_{i})$ , and hence $\mathcal{D}\leq c_{d}(n+\Phi)$ .

Proof.

Recall that $P_{i}(\mathbf{x})$ is the probability density function of a uniform distribution over a ball of radius $l_{i}$ . Thus, for $\mathbf{x}\in\mathcal{B}_{i}$ , $P_{i}(\mathbf{x})=\omega_{d}/l_{i}^{d}$ , where $\omega_{d}$ denotes the volume of the unit Euclidean ball in $\mathbb{R}^{d}$ , and $\mathcal{B}_{i}$ . Therefore,

$\displaystyle D_{i}$	$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathcal{B}_{i}}% P_{i}(\mathbf{x})\log\frac{P_{i}(\mathbf{x})}{H_{i}(\mathbf{x})}\mu(d\mathbf{x})$
	$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathcal{B}_{i}}% P_{i}(\mathbf{x})\log\frac{\omega_{d}/l_{i}^{d}}{(\pi^{d}h_{i}^{d})^{-1}\prod_% {j=1}^{d}\left({1+\frac{\left(x_{j}-{k}_{i,j}\right)^{2}}{h_{i}^{2}}}\right)^{% -1}}\mu(d\mathbf{x})$
	$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathcal{B}_{i}}% P_{i}(\mathbf{x})\log\left(\omega_{d}\kern 1.0pt\pi^{d}\right)\mu(d\mathbf{x})% \leavevmode\nobreak\ +\leavevmode\nobreak\ \int_{\mathcal{B}_{i}}P_{i}(\mathbf% {x})\log\frac{h_{i}^{d}\leavevmode\nobreak\ \prod_{j=1}^{d}\left({1+\frac{% \left(x_{j}-{k}_{i,j}\right)^{2}}{h_{i}^{2}}}\right)}{l_{i}^{d}}\mu(d\mathbf{x% }).$	(4)

For $\mathbf{x}\in\mathcal{B}_{i}$ and $j\in[d]$ , by the triangle inequality, we have

|x_{j}-{k}_{i,j}|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \|\mathbf{x}-% \mathbf{k}_{i}\|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \|\mathbf{x}-% \mathbf{q}_{i}\|+\|\mathbf{q}_{i}-\mathbf{k}_{i}\|\leavevmode\nobreak\ \leq% \leavevmode\nobreak\ l_{i}+s_{i}.

Therefore,

	$\displaystyle D_{i}$	$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \log\left(\omega_{d% }\kern 1.0pt\pi^{d}\right)\leavevmode\nobreak\ +\leavevmode\nobreak\ \int_{% \mathbf{x}\in\mathcal{B}_{i}}P_{i}(\mathbf{x})\log\left[\frac{h_{i}^{d}}{l_{i}% ^{d}}\kern 1.0pt\prod_{j=1}^{d}\left(1+\frac{\left(s_{i}+l_{i}\right)^{2}}{h_{% i}^{2}}\right)\right]\mu(d\mathbf{x})$
		$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \log\left(\omega_{d% }\kern 1.0pt\pi^{d}\right)\leavevmode\nobreak\ +\leavevmode\nobreak\ \log\left% [\frac{h_{i}^{d}}{l_{i}^{d}}\left(1+\frac{\left(s_{i}+l_{i}\right)^{2}}{h_{i}^% {2}}\right)^{\kern-2.0ptd}\right]\int_{\mathbf{x}\in\mathcal{B}_{i}}P_{i}(% \mathbf{x})\mu(d\mathbf{x})$
		$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \log\left(\omega_{d}% \leavevmode\nobreak\ \pi^{d}\right)\leavevmode\nobreak\ +\leavevmode\nobreak\ % d\log\left(\frac{h_{i}^{2}+\left(s_{i}+l_{i}\right)^{2}}{l_{i}\leavevmode% \nobreak\ h_{i}}\right)\leavevmode\nobreak\ \leq\leavevmode\nobreak\ c_{d}% \left(1+\log\frac{\max(s_{i},l_{i},h_{i})}{\sqrt{l_{i}h_{i}}}\right),$

for a suitably chosen $c_{d}$ that depends only on the dimension. $\hfill\blacktriangleleft$

$\blacktriangleright$ Remark (Potential function and approximating pairwise distances).

The potential function $\Phi_{i}$ we define here is symmetric. It is remarkable that a symmetric function bounds an asymmetric function $D_{i}$ under the choice of Cauchy distributions as hypotheses.

To demonstrate the value of our potential function, suppose that for $\forall i,\Phi_{i}<\log c$ , for some constant $c$ . This implies that $h_{i}<c\sqrt{l_{i}h_{i}}$ , which further implies $h_{i}<c^{\prime}l_{i}$ for some constant $c^{\prime}$ . Similarly, $s_{i}<c\sqrt{l_{i}h_{i}}<c^{\prime\prime}l_{i}$ for some constant $c^{\prime\prime}$ . By the triangle inequality, the distance between the centers of two hypothesis balls satisfies

\|\mathbf{k}_{i}-\mathbf{k}_{j}\|\leavevmode\nobreak\ \leq\leavevmode\nobreak% \ s_{i}+s_{j}+\|\mathbf{q}_{i}-\mathbf{q}_{j}\|\leavevmode\nobreak\ \leq% \leavevmode\nobreak\ c^{\prime\prime}l_{i}+c^{\prime\prime}l_{j}+\|\mathbf{q}_% {i}-\mathbf{q}_{j}\|.

Since $l_{i}=N_{i}/\beta\leq\|\mathbf{q}_{i}-\mathbf{q}_{j}\|/\beta$ , we have $\|\mathbf{k}_{i}-\mathbf{k}_{j}\|\leq c^{*}\|\mathbf{q}_{i}-\mathbf{q}_{j}\|$ , for some constant $c^{*}$ .

Since $\|\mathbf{k}_{i}-\mathbf{k}_{j}\|$ is a constant approximation for $\|\mathbf{q}_{i}-\mathbf{q}_{j}\|$ , it immediately follows that we can maintain a constant-weight approximation of structures like the Euclidean minimum spanning tree and the Euclidean traveling salesman tour on $Q$ by constructing the same on $\mathbf{k}_{i}$ ’s, the centers of the hypotheses $H_{i}$ ’s. $\lrcorner$

An important feature of our choice of a potential function is that the evolver cannot change its value by more than a constant with each step. Recall that the evolver selects an object index $i$ and moves $q_{i}$ by a distance of most $\alpha N_{i}$ in any direction. This results in at most an $\alpha$ fraction change in the values of $l_{i}$ and $s_{i}$ , and hence the resulting change in $\Phi_{i}$ is bounded by a constant. However, note that the movement of $q_{i}$ could potentially affect the local feature sizes of a number of other objects in the system. We can show by a packing argument that there is only a constant number of indices $j$ , whose $\Phi_{j}$ value is affected. Furthermore, these values are only changed by a constant. This is encapsulated in the following lemma. Its proof has been deferred to Section A.1.

Lemma 4.

Each step of the evolver increases the potential $\Phi$ by at most a constant.

4.2 The Algorithm

Next, we present our algorithm. The algorithm runs in parallel to the evolver, running faster by a speed-up factor of $\sigma$ (whose value will be derived in our analysis). Each step of the algorithm involves a probe of an object by the oracle, and following that, a possible modification of a hypothesis, $H_{i}$ . The total running time of the algorithm is proportional to the number of steps.

Let us begin with a high-level explanation. The details are provided in Algorithm˜TrackByZoom. Recall that we are given a set of $n$ objects, each represented by $X_{i}$ , a uniform probability distribution over a ball $\mathcal{B}_{i}=\mathcal{B}(\mathbf{q}_{i},\beta N_{i})$ , where $N_{i}$ is the distance to its nearest neighbor and $\beta$ is the local feature scale. The points $\mathbf{q}_{i}$ are restricted to lie within a bounding ball $\mathcal{B}_{0}$ centered at the origin. The algorithm maintains a hypothesis in the form of $n$ Cauchy distributions, each represented by a hypothesis ball $\mathcal{B}^{H}_{i}=\mathcal{B}(\mathbf{k}_{i},h_{i})$ , where $\mathbf{k}_{i}$ is the center of the distribution and $h_{i}$ is the distribution’s scaling parameter.

The algorithm begins with an initial hypothesis, where each hypothesis ball is just $\mathcal{B}_{0}$ . This reflects the fact that we effectively assume nothing about the location of $\mathbf{q}_{i}$ , except that it lies within the bounding ball. The algorithm then proceeds in a series of iterations, where each iteration handles all the $n$ indices in order. The handling of each index involves two processes, called zoom-out and zoom-in.

In the zoom-out process, we query the oracle on index $i$ to check whether (1) the sampled point $X_{i}$ lies within its hypothesis ball and (2) at least one other $X_{j}$ lies within a concentric ball whose radius is larger by a factor of $\frac{1}{\beta}$ . If so, we expand the hypothesis ball by a factor of $3/(1-2\beta)$ . (We show in Lemma 5 that this guarantees that the hypothesis ball $\mathcal{B}_{i}^{H}$ now contains the local feature ball $\mathcal{B}_{i}$ .) We then proceed to the zoom-in process. If not, we double the hypothesis ball and repeat (see Figure 3).

Algorithm TrackByZoom Tracking Evolving Distributions.

(a) Multiple stages of the zoom-out process starting at

t=0

. Stage

t=2

is the first time

\mathcal{B}^{H,(t)}_{i}

contains

X_{i}

, and its

1/\beta

-expansion contains

X_{j}

.

(b)

\mathcal{B}_{i}^{H,(3)}

is the hypothesis ball at the end of the zoom-out process. Note that

\mathcal{B}_{i}\subset\mathcal{B}_{i}^{H,(3)}

.

Figure 3: The zoom-out process of TrackByZoom (Line 6).

In the zoom-in process, we first check whether $X_{i}$ lies within the hypothesis ball. (The evolver could have moved $q_{i}$ .) If not, we return to the zoom-out process. If so, we next check the $\frac{1}{\beta}$ -expansion of this ball. If there is no other $X_{j}$ in this expanded ball, we accept the current hypothesis for $i$ , and go on to the next point in the set. (We show in Lemma 10 that $\Phi_{i}$ at this point in time is bounded by a constant). If there is such an $X_{j}$ however, we may need to shrink the hypothesis ball for the current index. We cover the hypothesis ball with a collection of $O(1)$ balls whose radii are smaller by a constant factor, and we test whether $X_{i}$ lies within any of them (see Figure 4). As soon as we find one, we shrink the hypothesis ball about this ball. We repeat this process until one of the earlier conditions applies (causing us to return to the zoom-out process or move on to the next point).

(a) Set of nested balls covering

\mathcal{B}_{i}^{H,(0)}

, which we call

\Psi

.

\operatorname{radius}(\Psi_{i})=\operatorname{radius}(\mathcal{B}_{i})/\left(2% \lceil\frac{3}{1-2\beta}\rceil\right)

, and

|\Psi|\in O(1)

.

(b)

\Psi_{k}

is the first nested ball to contain

X_{i}

.

\mathcal{B}^{H,(k)}_{i}

contains

X_{i}

, and its

1/\beta

-expansion does not contain

X_{j}

. TrackByZoom moves on to index

i+1

.

Figure 4: Illustration of the zoom-in process in TrackByZoom (Line 14).

4.3 Analysis

In this section, we analyze the distance that the algorithm maintains with the ground truth. Recall that the initial hypotheses are based on the bounding ball $\mathcal{B}_{0}$ , which is centered at the origin. Letting $R_{0}=\operatorname{radius}(\mathcal{B}_{0})$ , we have $H_{i}^{(0)}(\mathbf{x})=f_{\mathbf{0},R_{0}}(\mathbf{x})$ , as defined in Eq. (2: Hypothesis Def.). Using Eq. (3), the initial potential function satisfies:

\Phi_{i}^{(0)}=\log\sqrt{R_{0}/l_{i}^{(0)}},\quad\text{and}\quad\Phi^{(0)}\in O% (n\log\Lambda_{0})\quad\quad(\Lambda_{0}\text{:Aspect Ratio})

(5)

Suppose the condition in line 8, and 23 are satisfied. We prove the following lemma to justify the expansion factor $\frac{3}{1-2\beta}$ . The proof is rather technical and has been deferred to the full version of the paper.

Lemma 5 (Expansion Factor).

If $\mathcal{O}(i,\mathbf{k}_{i},h_{i})=(Y,\cdot)$ and $\mathcal{O}(i,\mathbf{k}_{i},h_{i}/\beta)=(Y,+)$ , then $\mathcal{B}_{i}\subseteq\mathcal{B}\left(\mathbf{k}_{i},\frac{3}{1-2\beta}h_{i% }\right)$ .

Let us consider how Algorithm˜TrackByZoom affects the potential. For a particular index $i$ , during the zoom-out process, we double the radius $h_{i}$ of the hypothesis ball. If the Euclidean distance between the centers of the hypothesis, and the local-feature ball is much larger than $h_{i}$ , then $\Phi=\log(\max(s_{i},l_{i},h_{i})/\sqrt{l_{i}h_{i}})=\log(s_{i}/\sqrt{l_{i}h_{% i}})$ decreases by an additive constant. However, once $h_{i}$ is greater than $s_{i}$ , the algorithm risks increasing $\Phi$ . We show that the number of steps where $\Phi$ increases is a constant for every index $i$ . However, during the zoom-in process, we maintain the invariant that the hypothesis ball contains the local-feature ball (Lemma 5), which implies that $\max(s_{i},l_{i},h_{i})=h_{i}$ . Therefore, $\Phi$ decreases by a constant amount whenever we shrink the hypothesis ball by a constant factor. However, if the evolver moves $q_{i}$ while index $i$ is being processed, our algorithm may transition to the zoom-out process again. Hence, if the evolver executes some $\varepsilon^{\langle z\rangle}$ steps in the $z$ th iteration, our algorithm may increase $\Phi$ by only $O\left(n+\varepsilon^{\langle z\rangle}\right)$ . We obtain the following lemma. The proof is deferred to Section A.1

Lemma 6 (Algorithm’s contribution towards $\Phi$ ).

For any iteration $z$ , let $\varepsilon^{\langle z\rangle}$ denote the number of steps executed by the evolver. Then TrackByZoom increases $\Phi$ in $O\left(n+\varepsilon^{\langle z\rangle}\right)$ steps, each time by $O(1)$ . In each of the remaining steps of the $z$ th iteration, it decreases $\Phi$ by $\Theta(1)$ in an amortized sense.

Let $\Phi^{\langle z\rangle}$ be the potential function at the start of the $z$ th iteration. And let $\Delta^{\langle z\rangle}$ be the time taken by the $z$ th iteration of the algorithm. At the conclusion of the zoom-in process for a particular index $i$ , the algorithm fixes a hypothesis $H_{i}$ which is at a reasonable distance from the truth $P_{i}$ . In fact, we show in Lemma 10 that at this point in time, $\Phi_{i}$ is $\phi_{0}$ , a constant. Therefore, by Lemma 6, TrackByZoom running at a constant speed-up $\sigma$ roughly spends $\sim\Phi^{\langle z\rangle}_{i}$ time (within constant factors), in reducing $\Phi^{\langle z\rangle}_{i}$ to $\phi_{0}$ . Summing over all indices, we see that the time taken by $z$ th iteration, $\Delta^{\langle z\rangle}$ , is $\sim\Phi^{\langle z\rangle}$ . Intuitively, for a sufficiently large speed-up factor, the actions of the evolver can only affect $\Delta^{\langle z\rangle}$ by a small fraction of this amount. We summarize these observations in the following lemma. The proof is deferred to Section A.1

Lemma 7 (Iteration time proportional to Potential).

There exists a constant speed-up factor $\sigma$ for TrackByZoom such that $\Delta^{\langle z\rangle}\in\Theta_{\sigma}\left(n+\Phi^{\langle z\rangle}\right)$ .

We are now ready to derive how $\Phi^{\langle z\rangle}$ changes over the course of multiple iterations. We show that for a sufficiently large (constant) speed-up factor $\sigma$ , after $\sim\log\log\Lambda_{0}$ iterations $\Phi$ converges to $O(n)$ . (Recall that $\Lambda_{0}$ is the initial aspect ratio.)

Lemma 8.

There exists a constant speed-up factor $\sigma$ for Algorithm˜TrackByZoom and $z_{0}\in\mathbb{Z}$ , such that for all $z>z_{0}$ , $\Phi^{\langle z\rangle}\in O(n)$

Proof.

By Lemma 4, in the $z$ th iteration the evolver takes at most $\varepsilon^{\langle z\rangle}=O(\Delta^{\langle z\rangle})$ steps and increases $\Phi$ by at most $O(\Delta^{\langle z\rangle})$ . Therefore, by Lemma 6, TrackByZoom increases $\Phi$ by $O(n+\Delta^{\langle z\rangle})$ . Since the algorithm runs at a speed-up factor $\sigma$ it takes $\sigma\Delta^{\langle z\rangle}$ steps, and by Lemma 6, it decreases $\Phi$ by at least $\lambda(\sigma\leavevmode\nobreak\ \Delta^{\langle z\rangle}-O(n+\Delta^{% \langle z\rangle}))$ , for some $\lambda\in O(1)$ . Accounting for all the increases and decreases we have:

	$\displaystyle\Phi^{\langle z+1\rangle}$	$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \Phi^{\langle z% \rangle}+O(\Delta^{\langle z\rangle})+O(n+\Delta^{\langle z\rangle})-\lambda(% \sigma\leavevmode\nobreak\ \Delta^{\langle z\rangle}-O(n+\Delta^{\langle z% \rangle}))$
		$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \Phi^{\langle z% \rangle}+O(\Delta^{\langle z\rangle})-\sigma\lambda\Delta^{\langle z\rangle}+O% (n).$

There exists a sufficiently large $\sigma\in O(1)$ such that $\sigma\lambda\Delta^{\langle z\rangle}-O(\Delta^{\langle z\rangle})\geq a% \Delta^{\langle z\rangle}$ , for $0<a\in O(1)$ . So,

\Phi^{\langle z+1\rangle}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \Phi^{% \langle z\rangle}-a\Delta^{\langle z\rangle}+O(n).

By Lemma 7, for a sufficiently large (constant) $\sigma$ , there exists $c_{\sigma}>0$ such that $\Delta^{\langle z\rangle}\geq c_{\sigma}\left(n+\Phi^{\langle z\rangle}\right)$ . Therefore,

\displaystyle\Phi^{\langle z+1\rangle}

\displaystyle\leq(1-ac_{\sigma})\Phi^{\langle z\rangle}+(1-ac_{\sigma})O(n)% \leq(1-ac_{\sigma})^{z+1}\Phi^{\langle 0\rangle}+\left(\sum_{y=1}^{z+1}(1-ac_{% \sigma})^{y}\right)O(n).

By Eq. (5), $\Phi^{\langle 0\rangle}=\Phi^{(0)}\in O(n\log\Lambda_{0})$ , and since there exists $b>1$ such that $(1-ac_{\sigma})<1/b<1$ , we have

\displaystyle\Phi^{\langle z+1\rangle}

\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \frac{O(n\log% \Lambda_{0})}{b^{z+1}}\leavevmode\nobreak\ +\leavevmode\nobreak\ O(n).

(6)

Observe that this is $O(n)$ whenever $z>\log\log\Lambda_{0}$ . $\hfill\blacktriangleleft$

If $\Phi^{\langle z\rangle}\in O(n)$ , then by Lemma 7, $\Delta^{\langle z\rangle}\in\Theta(n)$ . Thus, $\Phi$ increases by at most $O(n)$ throughout iteration $z$ . Therefore, for any time $t$ during iteration $z$ , $\Phi^{(t)}\in O(n)$ as well.

Using Eq. (6) we observe that for all $z>1$ , $\Phi^{\langle z\rangle}\leq O(n\log\Lambda_{0})$ . By Lemma 7, this implies that $\Delta^{\langle z\rangle}\in\Theta(n\log\Lambda_{0})$ . Hence, for some $t_{0}\in O(n\log\Lambda_{0}\cdot\log\log\Lambda_{0})$ , we have $\Phi^{(t)}\in O(n)$ , for all $t>t_{0}$ .

By combining Lemmas 8 and 3, we complete the proof of Theorem 1. It is noteworthy that there is a trade-off between the speed-up factor $\sigma$ and the motion parameter $\alpha$ . Recall that with each step, the evolver can move $q_{i}$ by a distance of up to $\alpha N_{i}$ . If we reduce this parameter to $\alpha^{\prime}=(1+\alpha)^{\frac{1}{c}}-1$ , then it takes the evolver at least $c$ steps to effect the same change as before. Thus, by reducing the local-motion factor, it is possible to achieve a speed-up factor of $\sigma=1$ . Formally we have,

Corollary 9.

There exists a motion parameter $\alpha^{\prime}<1$ such that for a set of $n$ evolving objects in $\mathbb{R}^{d}$ under the $(\alpha^{\prime},\beta)$ -local-motion model, where $\beta<\frac{1}{3}$ , Algorithm˜TrackByZoom (with speed-up factor 1) maintains a distance of $O(n)$ for all $t\geq t_{0}$ , $t_{0}\in O(n\log\Lambda_{0}\log\log\Lambda_{0})$

5 Extensions and Conclusion

The local-motion model introduced in Section 2 assumes a uniform probability distribution for each object. However, the algorithm TrackByZoom with an appropriate speed-up factor can be applied to a wider class of probability distributions. A distribution $P_{i}$ in this class has $\mathcal{B}_{i}$ , the volume of the $i$ th object, as its support, and is scaled according to $l_{i}$ , the local feature size. Many natural truncated distributions [11], such as the uniform distribution, the truncated normal distribution [27], the truncated Cauchy distribution belong to this family. Details are presented in the full version of the paper.

An additional refinement to the motion model we suggested might involve redefining the local feature region and the speed of a point based on the distance to its $k$ -nearest neighbors for a fixed $k$ , instead of just using the nearest neighbor distance. We conjecture that our principal results extend to this generalization as well, given a suitable range counting oracle. Yet another variation of the model could possibly involve letting the uncertainty associated with a point have unbounded support (for e.g. a normal rather than a truncated normal distribution). This is a significantly harder problem, as a point may lie outside its local feature with a constant probability, requiring a maintaining algorithm to have a super-constant speed-up. We aim to study these in the future.

References

[1] A. Acharya and D. M. Mount. Optimally tracking labels on an evolving tree. In Proc. 34th Canad. Conf. Comput. Geom., pages 1–8, 2022.
[2] A. Anagnostopoulos, R. Kumar, M. Mahdian, and E. Upfal. Sorting and selection on dynamic data. Theoretical Computer Science, 412(24):2564–2576, 2011. doi:10.1016/j.tcs.2010.10.003.
[3] A. Anagnostopoulos, R. Kumar, M. Mahdian, E. Upfal, and F. Vandin. Algorithms on evolving graphs. In Proc. 3rd Innov. Theor. Comput. Sci. Conf., pages 149–160, 2012. doi:10.1145/2090236.2090249.
[4] M. Beermann and A. Sieben. The connection between stress, density, and speed in crowds. Scientific Reports, 13:13626, 2023. doi:10.1038/s41598-023-39006-8.
[5] J. J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson. Optimally sorting evolving data. In 45th Internat. Colloq. Autom., Lang., and Prog., pages 81:1–81:13, 2018. doi:10.4230/LIPIcs.ICALP.2018.81.
[6] J. J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson. Quadratic time algorithms appear to be optimal for sorting evolving data. In Proc. 20th Workshop Algorithm Eng. and Exp., pages 87–96, 2018.
[7] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 2005.
[8] K. Buchin, M. Löffler, P. Morin, and W. Mulzer. Delaunay triangulation of imprecise points simplified and extended. Algorithmica, 61:674–693, 2011. doi:10.1007/s00453-010-9430-0.
[9] D. Busto, W. Evans, and D. Kirkpatrick. Minimizing interference potential among moving entities. In Proc. 30th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 2400–2418, 2019. doi:10.5555/3310435.3310582.
[10] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 2012. doi:10.1002/047174882X.
[11] Y. Dodge. The Oxford Dictionary of Statistical Terms. Oxford Univ. Press, 2003. doi:10.1002/sim.1812.
[12] W. Evans and D. Kirkpatrick. Minimizing query frequency to bound congestion potential for moving entities at a fixed target time. Algorithms, 17:246, 2024. doi:10.3390/a17060246.
[13] J. Gudmundsson, P. Laube, and T. Wolle. Computational movement analysis. In W. Kresse and D. Danko, editors, Handbook of Geogr. Inf., pages 725–741. Springer, 2012. doi:10.1007/978-3-540-72680-7_22.
[14] L. J. Guibas, D. Salesin, and J. Stolfi. Epsilon geometry: Building robust algorithms from imprecise computations. In Proc. Fifth Annu. Sympos. Comput. Geom., pages 208–217, 1989. doi:10.1145/73833.73857.
[15] D. Helbing, L. Buzna, A. Johansson, and T. Werner. Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Science, 39:1–24, 2005. doi:10.1287/trsc.1040.0108.
[16] O. Hesham and G. Wainer. Context-sensitive personal space for dense crowd simulation. In Proc. Symp. Simulation for Architecture and Urban Design, pages 1–8, 2017. URL: https://dl.acm.org/doi/10.5555/3289787.3289806.
[17] Q. Huang, X. Liu, X. Sun, and J. Zhang. Partial sorting problem on evolving data. Algorithmica, 79:960–983, 2017. doi:10.1007/s00453-017-0295-3.
[18] D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40:1098–1101, 1952. doi:10.1109/JRPROC.1952.273898.
[19] U. Jain. Effects of population density and resources on the feeling of crowding and personal space. J. Social Psych., 127:331–338, 1987. doi:10.1080/00224545.1987.9713699.
[20] S. Kahan. A model for data in motion. In Proc. 23rd Annu. ACM Sympos. Theory Comput., pages 265–277, 1991. doi:10.1145/103418.103449.
[21] V. Kanade, N. Leonardos, and F. Magniez. Stable matching with evolving preferences. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016.
[22] M. G. Kendall. A new measure of rank correlation. Biometrika, 30:81–93, 1938. doi:10.2307/2332226.
[23] S. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Statist., 22:79–86, 1951. doi:10.1214/aoms/1177729694.
[24] P. Laube. Computational Movement Analysis. Springer Cham, 2014. doi:10.1007/978-3-319-10268-9.
[25] M. Löffler and M. van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56:235–269, 2010. doi:10.1007/s00453-008-9174-2.
[26] D. J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. URL: https://books.google.com/books?id=AKuMj4PN_EMC.
[27] F. Nielsen. Statistical divergences between densities of truncated exponential families with nested supports: Duo Bregman and duo Jensen divergences. Entropy, 24:421, 2022. doi:10.3390/e24030421.
[28] R. Pan, Z. Han, T. Liu, H. Wang, J. Huang, and W. Wang. An RFID tag movement trajectory tracking method based on multiple RF characteristics for electronic vehicle identification ITS applications. Sensors, 23:7001, 2023. doi:10.3390/s23157001.
[29] A. Seyfried, B. Steffen, W. Klingsch, and M. Boltes. The fundamental diagram of pedestrian movement revisited. J. Stat. Mech. Theory Exp., 2005:P10002, 2005. doi:10.1088/1742-5468/2005/10/P10002.
[30] C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:623–656, 1948. doi:10.1002/j.1538-7305.1948.tb00917.x.
[31] S. M. Tomkiewicz, M. R. Fuller, J. G. Kie, and K. K. Bates. Global positioning system and associated technologies in animal behaviour and ecological research. Phil. Trans. R. Soc. B, 365:2163–2176, 2010. doi:10.1098/rstb.2010.0090.
[32] M. van Kreveld, M. Löffler, F. Staals, and L. Wiratma. A refined definition for groups of moving entities and its computation. Internat. J. Comput. Geom. Appl., 28(2):181–196, 2018. doi:10.4230/LIPIcs.ISAAC.2016.130.
[33] S. Verdú. The Cauchy distribution in information theory. Entropy, 25:346, 2023. doi:10.3390/e25020346.
[34] L. Wiratma, M. Löffler, and F. Staals. An experimental comparison of two definitions for groups of moving entities. In Proc. 10th Internat. Conf. Geogr. Inf. Sci., pages 64:1–64:6, 2018. doi:10.4230/LIPIcs.GIScience.2018.64.
[35] S. Yi, H. Li, and X. Wang. Understanding pedestrian behaviors from stationary crowd groups. In Proc. IEEE Conf. Comput. Vis. Pattern Recogn., pages 3488–3496, 2015. doi:10.1109/CVPR.2015.7298971.
[36] Y. Zou, G. Zeng, Y. Wang, X. Liu, X. Sun, J. Zhang, and Q. Li. Shortest paths on evolving graphs. In H. T. Nguyen and V. Snasel, editors, Computational Social Networks, pages 1–13. Springer, 2016. doi:10.1007/978-3-319-42345-6_1.

Appendix A Appendix

A.1 Deferred Proofs

Note that some of the restatements of the lemmas given here provide additional details, which were not present in the original statements.

The next lemma applies whenever Algorithm˜TrackByZoom has completed its processing of an object on Line 20. It shows that the potential value for this object does not exceed a constant.

Lemma 10 (Done tracking $X_{i}$ ).

There exists a constant $\phi_{0}$ , such that whenever Algorithm˜TrackByZoom completes its processing of any object $i$ , $\Phi_{i}\leq\phi_{0}\in O(1)$ .

Proof.

The algorithm moves on to the next point when the condition in line 19 is satisfied ( $\mathcal{O}(i,\mathbf{k}_{i},h_{i})=(Y,\cdot)$ and $\mathcal{O}(i,\mathbf{k}_{i},h_{i}/\beta)=(Y,-)$ ). Since $\mathcal{O}(i,\mathbf{k}_{i},h_{i})=(Y,\cdot)$ , $\mathcal{B}^{H}_{i}=\mathcal{B}(\mathbf{k}_{i},h_{i})$ intersect. Moreover, if $\mathbf{q}_{j}$ is the current nearest neighbor of $\mathbf{q}_{i}$ , $\mathcal{O}(i,\mathbf{k}_{i},h_{i}/\beta)=(Y,-)$ implies $X_{j}$ lies outside the $1/\beta$ expansion of $\mathcal{B}^{H}_{i}$ (see Figure 5).

Figure 5: Proof of Lemma 10.

Now because $\mathbf{q}_{j}$ is the nearest neighbor of $\mathbf{q}_{i}$ , $N_{j}\leq N_{i}$ , hence $l_{j}\leq l_{i}$ . By triangle inequality, the following series of inequality holds:

\frac{h_{i}}{\beta}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \|X_{j}-% \mathbf{k}_{i}\|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \|X_{j}-\mathbf{% q}_{i}\|+\|\mathbf{q}_{i}-\mathbf{k}_{i}\|\leavevmode\nobreak\ \leq\leavevmode% \nobreak\ \left(\frac{l_{i}}{\beta}+l_{j}\right)+\left(h_{i}+l_{i}\right)% \leavevmode\nobreak\ \leq\leavevmode\nobreak\ \left(\frac{1}{\beta}+2\right)l_% {i}+h_{i},

implying that $\frac{1-\beta}{1+2\beta}h_{i}\leq l_{i}$ .

Now consider the hypothesis ball, $\mathcal{B}^{H^{-}}_{i}$ , set by the algorithm in the previous step (via Line 26). From Lemma 5, we have $\mathcal{B}_{i}\subseteq\mathcal{B}^{H^{-}}_{i}$ . Let $h_{i}^{-}=\operatorname{radius}\left(\mathcal{B}^{H^{-}}_{i}\right)$ . Since the algorithm shrinks the hypothesis ball by at least a factor of 2 during the zoom-in process, $h_{i}^{-}$ is at least $2h_{i}$ . And therefore $2h_{i}\geq l_{i}$ . We also have $s_{i}\leq h_{i}+l_{i}$ (see Figure 5). Therefore,

	$\displaystyle\Phi_{i}=\log\left(\frac{\max(s_{i},l_{i},h_{i})}{\sqrt{l_{i}h_{i% }}}\right)$	$\displaystyle\leq\log\left(\frac{l_{i}+h_{i}}{\sqrt{l_{i}h_{i}}}\right)$
		$\displaystyle\leq\log\left(\frac{2h_{i}+h_{i}}{\sqrt{\frac{1-\beta}{1+2\beta}h% _{i}\cdot h_{i}}}\right)\leq\phi_{0},\quad\text{for }\phi_{0}=\log\left(3\cdot% \sqrt{\frac{1+2\beta}{1-\beta}}\right).\$

$\hfill\blacktriangleleft$

Theorem 2 (Lower Bound on the Distance).

For any algorithm $\mathcal{A}$ , there exists a starting configuration $Q^{(0)}$ and an evolver (with knowledge of $\mathcal{A}$ ) in the local-motion model such that, for any positive integer $t_{0}$ , there exists $t\geq t_{0}$ , such that $\mathcal{D}^{(t)}=\mathcal{D}(\mathcal{P}^{(t)},\mathcal{H}^{(t)})\in\Omega(n)$ .

Proof.

We construct a point set on the real line ( $\mathbb{R}$ ), and we will mention at the end how to adapt the proof to any dimension $d$ . Given the small constant $\beta$ , the local feature constant, we define $Q^{(0)}$ to be the following set of $n=2m$ points in $\mathbb{R}$ .

Q^{(0)}\leavevmode\nobreak\ =\leavevmode\nobreak\ \bigcup_{i\in[m]}\left\{a_{i% }^{(0)}=100i\right\}\cup\bigcup_{i\in[m]}\left\{b_{i}^{(0)}=100i+1\right\}.

Let $\mathcal{D}_{a,i}=\mathcal{D}_{2(k-1)+1},\;k\in[m]$ , the distance corresponding to the first point in the tuple. We similarly define $P_{a,i}$ and $H_{a,i}$ . Let $N_{i}$ denote the current distance to $a_{i}$ ’s nearest neighbor. The local feature interval for $a_{i}$ , denoted $I_{i}$ , is $100i+\beta N_{i}[-1,1]$ . Recall that $P_{a,i}$ is the uniform probability over $I_{i}$ . Therefore, $P_{a,i}(\mathbf{x})=1/|\mathcal{I}_{i}|$ , where $|\mathcal{I}_{i}|=1/\beta N_{i}$ is the diameter of $\mathcal{I}_{i}$ . Now

	$\displaystyle\mathcal{D}^{(t_{0})}_{a,i}$	$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathbf{x}\in% \mathcal{I}_{i}}P^{(t_{0})}_{a,i}(\mathbf{x})\log\frac{P^{(t_{0})}_{a,i}(% \mathbf{x})}{H^{(t_{0})}_{a,i}(\mathbf{x})}d\mathbf{x}$
		$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ \int_{\mathbf{x}\in% \mathcal{I}_{i}}P^{(t_{0})}_{a,i}(\mathbf{x})\log P^{(t_{0})}_{a,i}(\mathbf{x}% )d\mathbf{x}\leavevmode\nobreak\ -\leavevmode\nobreak\ \int_{\mathbf{x}\in% \mathcal{I}_{i}}P^{(t_{0})}_{a,i}(\mathbf{x})\log H^{(t_{0})}_{a,i}(\mathbf{x}% )d\mathbf{x}.$

By the concavity of the log function and Jensen’s inequality, we have

	$\displaystyle\mathcal{D}^{(t_{0})}_{a,i}$	$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\ -\log\|\mathcal{I}_{% i}\|\int_{\mathbf{x}\in\mathcal{I}_{i}}P^{(t_{0})}_{a,i}(\mathbf{x})d\mathbf{x}% \leavevmode\nobreak\ -\leavevmode\nobreak\ \log\int_{\mathbf{x}\in\mathcal{I}_% {i}}H^{(t_{0})}_{a,i}(\mathbf{x})P^{(t_{0})}_{a,i}(\mathbf{x})d\mathbf{x}$
		$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ -\log\|\mathcal{I}_{i}\|% -\log\frac{\int_{\mathbf{x}\in\mathcal{I}_{i}}H^{(t_{0})}_{a,i}(\mathbf{x})d% \mathbf{x}}{\|\mathcal{I}_{i}\|}\leavevmode\nobreak\ =\leavevmode\nobreak\ -\log% \int_{\mathbf{x}\in\mathcal{I}_{i}}H^{(t_{0})}_{a,i}(\mathbf{x})d\mathbf{x}.$		(7)

We may assume that $\mathcal{D}^{(t_{0})}\in o(n)$ (for otherwise we can set $t={t_{0}}$ and are done). This implies there are only $o(n)$ many $a_{i}$ ’s such that $\mathcal{D}^{(t_{0})}_{a,i}\in\Omega(1)$ . Call the remaining $n/2-o(n)$ , $a_{i}$ ’s the proximal set, denoted $T_{a}$ .

We are now ready to describe the evolver’s actions. It chooses to stay dormant until time ${t_{0}}$ . For a large enough constant $M$ , consider the time interval $[{t_{0}},{t_{0}}+n/M]$ . The algorithm $\mathcal{A}$ , running at a speed-up factor of $\sigma$ , can modify at most $\sigma n/M$ hypotheses in the time interval. The evolver chooses not to move any of those points. Therefore $\mathcal{A}$ can only reduce $\mathcal{D}^{(t_{0})}$ by $o(n)$ over this time interval. Now there are at least $n/2-\sigma n/M-o(n)$ members in the proximal set $T_{a}$ , whose hypotheses were not altered by $\mathcal{A}$ . Call this set the stable set, denoted $S_{a}$ .

For $\kappa=\lceil\log(2/(1+\alpha))\rceil$ , the evolver selects some $n/(\kappa M)$ members from $S_{a}$ . Call that set $S^{\prime}_{a}$ . To be specific, for all $a_{i}\in S^{\prime}_{a}$ , the evolver chooses to move $a_{i}$ away from $b_{i}$ some $\kappa$ times, by a distance of exactly $\alpha N_{a,i}$ , where $N_{a,i}$ is the distance of $a_{i}$ from its current nearest neighbor. (Note that the nearest neighbor will remain $b_{i}$ throughout these operations.) Given this value of $\kappa$ , after the conclusion of these operations, the distance between $a_{i}$ and $b_{i}$ is at least 2. For $\beta<1/3$ , the local feature of $a_{i}$ changes to an interval $\mathcal{I}^{\prime}_{i}$ , where $\mathcal{I}^{\prime}_{i}\cap\mathcal{I}_{i}=\emptyset$ . Now, for $t={t_{0}}+n/M$ , using a similar analysis as Eq. (7), we have

\mathcal{D}^{(t)}_{a,i}\leavevmode\nobreak\ \geq\leavevmode\nobreak\ -\log\int% _{\mathbf{x}\in\mathcal{I}^{\prime}_{i}}H^{(t)}_{a,i}(\mathbf{x})d\mathbf{x}.

(8)

Thus, for all $a_{i}\in S^{\prime}_{a}$ , we have $H^{(t)}_{a,i}=H^{(t_{0})}_{a,i}$ and $D^{(t_{0})}_{a,i}=o(1)$ . Therefore,

\int_{\mathbf{x}\in\mathcal{I}_{i}}H^{(t_{0})}_{a,i}(\mathbf{x})d\mathbf{x}% \leavevmode\nobreak\ \geq\leavevmode\nobreak\ e^{-o(1)}.

If $\mathcal{D}^{(t)}_{a,i}\in o(1)$ as well, then similarly from Eq. (8), we have

\int_{\mathbf{x}\in\mathcal{I}^{\prime}_{i}}H^{(t)}_{a,i}(\mathbf{x})d\mathbf{% x}\leavevmode\nobreak\ \geq\leavevmode\nobreak\ e^{-o(1)}.

But, this yields a contradiction since $\mathcal{I}^{\prime}_{i}\cap\mathcal{I}_{i}=\emptyset$ and $H^{(t)}_{a,i}=H^{(t_{0})}_{a,i}$ implies that

\int_{\mathbf{x}\in\mathcal{I}^{\prime}_{i}\cup\mathcal{I}_{i}}H^{(t)}_{a,i}(% \mathbf{x})d\mathbf{x}\leavevmode\nobreak\ \geq\leavevmode\nobreak\ 2e^{-o(1)}% \leavevmode\nobreak\ >\leavevmode\nobreak\ 1.

Therefore, for $a_{i}\in S^{\prime}_{a}$ , $\mathcal{D}^{(t)}_{a,i}\in\Omega(1)$ , and since $|S^{\prime}_{a}|=\Omega(n)$ , we have $\mathcal{D}^{(t)}\in\Omega(n)$ .

For a general dimension $d$ , we define $Q$ , in the same way except all the points lie on a single axis. The evolver also moves these points along that particular axis. The rest of the analysis involves integration over a region of space rather an interval, but is straightforward and carries over to $\mathbb{R}^{d}$ . $\hfill\blacktriangleleft$

Lemma 11 (Evolver’s contribution to $\Phi$ ).

Every step of the evolver increases the potential function $\Phi$ by at most a constant.

Proof.

Let’s say the evolver chooses to move $\mathbf{q}_{i}$ at time $0$ . Now $l^{(0)}_{i}/\beta$ is the nearest neighbor distance of $\mathbf{q}_{i}$ at time $0$ . Therefore $\mathbf{q}_{i}$ moves by at most $(\alpha/\beta)l^{(0)}_{i}$ distance, implying $s_{i}^{(1)}\leq s_{i}^{(0)}+(\alpha/\beta)l_{i}^{(0)}\leq\left(1+\alpha/\beta% \right)\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}\right)$ . Similarly $(1-\alpha)l_{i}^{(0)}\leq l_{i}^{(1)}\leq(1+\alpha)l_{i}^{(0)}$ . Therefore,

\displaystyle\begin{split}\Phi_{i}^{(1)}-\Phi_{i}^{(0)}&\leavevmode\nobreak\ % \leq\leavevmode\nobreak\ \log\frac{\max\left(s_{i}^{(1)},l_{i}^{(1)},h_{i}^{(1% )}\right)}{\sqrt{l_{i}^{(1)}h_{i}^{(1)}}}-\log\frac{\max\left(s_{i}^{(0)},l_{i% }^{(0)},h_{i}^{(0)}\right)}{\sqrt{l_{i}^{(0)}h_{i}^{(0)}}}\\ &\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \log\frac{\max\left(s_{i}^{(0)}% +(\alpha/\beta)l_{i}^{(0)},(1+\alpha)l_{i}^{(0)},h_{i}^{(0)}\right)}{\sqrt{(1-% \alpha)l_{i}^{(0)}h_{i}^{(0)}}}\leavevmode\nobreak\ -\leavevmode\nobreak\ \log% \frac{\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}\right)}{\sqrt{l_{i}^{(0)}h% _{i}^{(0)}}}\\ &\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \log\left(\frac{1+\alpha/\beta}% {\sqrt{1-\alpha}}\frac{\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}\right)}{% \sqrt{l_{i}^{(0)}h_{i}^{(0)}}}\right)\leavevmode\nobreak\ -\leavevmode\nobreak% \ \log\frac{\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}\right)}{\sqrt{l_{i}^% {(0)}h_{i}^{(0)}}}\\ &\leavevmode\nobreak\ =\leavevmode\nobreak\ \log\frac{1+\alpha/\beta}{\sqrt{1-% \alpha}}\in O(1)\end{split}

(9)

Let $\mathcal{N}_{i}$ be the set of indices of points whose nearest neighbor at time 0 was $\mathbf{q}_{i}^{(0)}$ , or whose nearest neighbor at time 1 was $\mathbf{q}_{i}^{(1)}$ . Only points with indices in this set have their potential function changed. If $j\in\mathcal{N}_{i}$ , $s_{j}^{(0)}$ , and $h_{j}^{(0)}$ do not change. Since $\mathbf{q}_{i}$ moves by at most $(\alpha/\beta)l^{(0)}_{i}$ distance, the nearest neighbor distance $N_{j}=l_{j}/\beta$ changes by at most $(\alpha/\beta)l^{(0)}_{i}$ as well. Therefore,

	$\displaystyle-(\alpha/\beta)l_{i}^{(0)}\leavevmode\nobreak\ \leq\leavevmode% \nobreak\ N_{j}^{(1)}-N_{j}^{(0)}\leavevmode\nobreak\ \leq\leavevmode\nobreak% \ (\alpha/\beta)l_{i}^{(0)}\leavevmode\nobreak\ \implies\leavevmode\nobreak\ -% \alpha l_{i}^{(0)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ l_{j}^{(1)}-l_% {j}^{(0)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \alpha l_{i}^{(0)}$	(10)
Since $(1-\alpha)l_{i}^{(0)}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ l_{i}^{(1)}$ , we also have
	$\displaystyle-\frac{\alpha}{1-\alpha}l_{i}^{(1)}\leavevmode\nobreak\ \leq% \leavevmode\nobreak\ l_{j}^{(1)}-l_{j}^{(0)}\leavevmode\nobreak\ \leq% \leavevmode\nobreak\ \frac{\alpha}{1-\alpha}l_{i}^{(1)}$	(11)

If $\mathbf{q}_{i}^{(0)}$ was the nearest neighbor of $\mathbf{q}_{j}^{(0)}$ , then $N_{j}^{(0)}\leq N_{i}^{(0)}$ , and hence $l_{j}^{(0)}\leq l_{i}^{(0)}$ . Using the last fact, and dividing Eq. (10) by $l_{j}^{(0)}$ , we have $(1-\alpha)\leq l_{j}^{(1)}/l_{j}^{(0)}\leq(1+\alpha)$ . Similarly, If $\mathbf{q}_{i}^{(1)}$ was the nearest neighbor of $\mathbf{q}_{j}^{(1)}$ , then using Eq. (11) we have $(1-\alpha/(1-\alpha))\leq l_{j}^{(1)}/l_{j}^{(0)}\leq(1+\alpha/(1-\alpha))$ . Therefore $l_{j}^{(1)}/l_{j}^{(0)}\in\Theta(1)$ for $j\in\mathcal{N}_{i}$ . And hence,

\displaystyle\begin{split}\Phi_{j}^{(1)}-\Phi_{j}^{(0)}&\leavevmode\nobreak\ =% \leavevmode\nobreak\ \log\frac{\max\left(s_{i}^{(1)},l_{i}^{(1)},h_{i}^{(1)}% \right)}{\sqrt{l_{i}^{(1)}h_{i}^{(1)}}}\leavevmode\nobreak\ -\leavevmode% \nobreak\ \log\frac{\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}\right)}{% \sqrt{l_{i}^{(0)}h_{i}^{(0)}}}\\ &\leavevmode\nobreak\ =\leavevmode\nobreak\ \log\frac{\max\left(s_{i}^{(0)},l_% {i}^{(1)},h_{i}^{(0)}\right)}{\max\left(s_{i}^{(0)},l_{i}^{(0)},h_{i}^{(0)}% \right)}\leavevmode\nobreak\ -\leavevmode\nobreak\ \log\frac{\sqrt{l_{i}^{(1)}% h_{i}^{(0)}}}{\sqrt{l_{i}^{(0)}h_{i}^{(0)}}}\\ &\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \left|\log\frac{l_{i}^{(1)}}{l_% {i}^{(0)}}\right|\leavevmode\nobreak\ +\leavevmode\nobreak\ \left|\log\frac{l_% {i}^{(0)}}{l_{i}^{(1)}}\right|\leavevmode\nobreak\ \in\leavevmode\nobreak\ O(1% ),\quad\forall\leavevmode\nobreak\ j\in\mathcal{N}_{i}\end{split}

(12)

Finally, we show that $|\mathcal{N}_{i}|\in O(1)$ . To that effect we solve a general problem: What is the maximum number of points in $Q$ , whose nearest neighbor is $\mathbf{q}_{1}$ ? Without loss of generality, let $\mathbf{q}_{2}$ be the nearest neighbor of $\mathbf{q}_{1}$ , such that $\|\mathbf{q}_{2}-\mathbf{q}_{1}\|=1$ . Let $\mathbf{q}_{3}$ ’s nearest neighbor be $\mathbf{q}_{1}$ . Consider the line segment $\overline{\mathbf{q}_{1}\mathbf{q}_{3}}$ , and its intersection with $\mathcal{B}(\mathbf{q}_{1},1)$ the ball centered at $\mathbf{q}_{1}$ , and passing through $\mathbf{q}_{2}$ . Call the intersection point $\mathbf{q}_{3}^{\prime}$ . For any general point $\mathbf{q}_{x}\in Q$ , we similarly define $\mathbf{q}_{x}^{\prime}$ . Note $\mathbf{q}_{2}^{\prime}=\mathbf{q}_{2}$ . By triangle inequality, we have $\|\mathbf{q}_{3}^{\prime}-\mathbf{q}_{2}^{\prime}\|\geq\|\mathbf{q}_{3}-% \mathbf{q}_{2}\|-\|\mathbf{q}_{3}-\mathbf{q}_{3}^{\prime}\|=\|\mathbf{q}_{3}-% \mathbf{q}_{2}\|-\|\mathbf{q}_{3}-\mathbf{q}_{1}\|+\|\mathbf{q}_{1}-\mathbf{q}% _{3}^{\prime}\|$ . Since $\mathbf{q}_{1}$ is the nearest neighbor of $\mathbf{q}_{3}$ , we have $\|\mathbf{q}_{3}-\mathbf{q}_{2}\|\geq\|\mathbf{q}_{3}-\mathbf{q}_{1}\|$ . Therefore $\|\mathbf{q}_{3}^{\prime}-\mathbf{q}_{2}^{\prime}\|\geq\|\mathbf{q}_{1}-% \mathbf{q}_{3}^{\prime}\|=1$ . Therefore, for any $x,y\in[n],x\neq y$ , such that $\mathbf{q}_{1}$ is the nearest neighbor of $\mathbf{q}_{x}$ and $\mathbf{q}_{y}$ , we have $\|\mathbf{q}_{x}^{\prime}-\mathbf{q}_{y}^{\prime}\|\geq 1$ . Let $\mathcal{M}_{1}=\{\mathbf{q}_{x}^{\prime}\mid\mathbf{q}_{1}\text{is the % nearest neighbor of }\mathbf{q}_{x}\}$ . Draw a ball of radius 1/2 around $\mathbf{q}_{1}$ , and every member of $\mathcal{M}_{1}$ . Each of these balls are non-overlapping. However all of them are contained within a ball around $\mathbf{q}_{1}$ of radius $3/2$ . Therefore $|\mathcal{M}_{1}|<(3/2)^{d}/(1/2)^{d}=3^{d}\in O(1)$ . Observing that $\mathcal{N}_{i}\leq 2\mathcal{M}_{1}$ , and using Eq. (9), and 12 we have the result. $\hfill\blacktriangleleft$

Lemma 12 (Algorithm’s contribution towards $\Phi$ ).

For any iteration $z$ , let $\varepsilon^{\langle z\rangle}$ denote the number of steps executed by the evolver. Then TrackByZoom increases $\Phi$ in $O\left(n+\varepsilon^{\langle z\rangle}\right)$ steps, each time by $O(1)$ . In each of the remaining steps of the $z$ th iteration, it decreases $\Phi$ by $\Theta(1)$ in an amortized sense.

Proof.

For a particular index $i$ , we first concentrate on the zoom-out routine of our Algorithm˜TrackByZoom (see Line 6). Assume that the evolver leaves $q_{i}$ untouched for the time being. We show later how to handle the case where the evolver moves $q_{i}$ , while the algorithm is processing the index $i$ . The algorithm increases $h_{i}$ by a constant factor in Line 12. Therefore, $\Phi=\log(\max(s_{i},l_{i},h_{i})/\sqrt{l_{i}h_{i}})$ decreases by a constant amount whenever $\max(s_{i},l_{i},h_{i})\neq h_{i}$ . Now suppose $\max(s_{i},l_{i},h_{i})=h_{i}$ at time $t$ , for the first time during the zoom-out routine. That implies a 2-expansion of $\mathcal{B}^{H}_{i}$ in line 12 contains the entire $\mathcal{B}_{i}$ . Therefore, a further $1/\beta$ -expansion definitely contains another $X_{j}$ , $j\neq i$ , satisfying the condition in line 8. We conclude that once $\max(s_{i},l_{i},h_{i})=h_{i}$ , the algorithm only increases $\Phi$ by a constant amount before moving on to the zoom-in routine of the algorithm (line 14).

Now, we look at the zoom-in routine of the algorithm (line 14). The algorithm only zooms in as long as the condition in line 23 is satisfied. Since we expand $\mathcal{B}_{i}^{H}$ with an expansion factor $\frac{3}{1-2\beta}$ in line 26, using Lemma 5 we conclude that $\mathcal{B}_{i}\subset\mathcal{B}_{i}^{H}$ in every step during the zoom-in routine. That implies $\max(s_{i},l_{i},h_{i})=h_{i}$ throughout the zoom-in process, further implying $\Phi_{i}=\log\sqrt{h_{i}/l_{i}}$ .

In line 24 we subdivide the hypothesis ball into $|\Psi|=\left(2\lceil\frac{3}{1-2\beta}\rceil\sqrt{d}\right)^{d}\in O(1)$ balls and make constant number of queries to the oracle. Therefore, $h_{i}$ reduces by a factor of $\frac{3}{1-2\beta}/\left(2\lceil\frac{3}{1-2\beta}\rceil\right)\geq 2$ . And hence, $\Phi$ reduces by at least a constant amount. We amortize the reduction over the $|\Psi|$ calls to the Oracle, to denote a constant reduction in $\Phi$ in every zoom-in step.

If the evolver moved $q_{i}$ while the algorithm was processing the index $i$ , there is a possibility that $X_{i}$ might move outside of $\mathcal{B}^{H}_{i}$ during the zoom-in routine. We take care of this condition in line 16 to initiate the zoom-out process. Since the algorithm possibly increases $\Phi$ by a constant amount when switching from zoom-out to zoom-in, we conclude: For every evolver’s step, our algorithm might increase $\Phi$ by at most a constant amount as well. $\hfill\blacktriangleleft$

Lemma 13 (Iteration time proportional to Potential).

There exists a constant speed-up factor $\sigma$ for TrackByZoom such that $\Delta^{\langle z\rangle}\in\Theta_{\sigma}\left(n+\Phi^{\langle z\rangle}\right)$ .

Proof.

By Lemma 4, the evolver can only increase the potential by $\Phi_{\varepsilon}^{\langle z\rangle}=O(\Delta^{\langle z\rangle})$ during the iteration. By Lemma 6 we observe that the algorithm increases $\Phi$ by some amount that is $O(n+\Delta^{\langle z\rangle})$ . Since by Lemma 10, the algorithm reduces each $\Phi_{i}$ to at most $\phi_{0}$ , it reduces the overall potential by at most $\Phi^{\langle z\rangle}-n\phi_{0}+\Phi_{\varepsilon}^{\langle z\rangle}+O(n+% \Delta^{\langle z\rangle})$ $=O(n+\Phi^{\langle z\rangle}+\Delta^{\langle z\rangle})$ . For a speed-up factor $\sigma$ , the algorithm TrackByZoom spends $O(n+\Phi^{\langle z\rangle}+\Delta^{\langle z\rangle})/\sigma$ time to do so, implying $\Delta^{\langle z\rangle}\leq O(n+\Phi^{\langle z\rangle}+\Delta^{\langle z% \rangle})/\sigma$ , further implying $\Delta^{\langle z\rangle}\in O_{\sigma}(n+\Phi^{\langle z\rangle})$ , for a sufficiently large constant $\sigma$ .

To see why $\Delta^{\langle z\rangle}\in\Omega(n+\Phi^{\langle z\rangle})$ , we follow a similar logic, except to observe that the evolver can decrease the potential by at most $\Phi_{\varepsilon}^{\langle z\rangle}=O(\Delta^{\langle z\rangle})$ as well. By Lemma 10, the algorithm reduces the overall potential $\Phi$ by at least $\Phi^{\langle z\rangle}-n\phi_{0}-\Phi_{\varepsilon}^{\langle z\rangle}=\Omega% (n+\Phi^{\langle z\rangle}-\Delta^{\langle z\rangle})$ , which takes it at least $\Omega(n+\Phi^{\langle z\rangle}-\Delta^{\langle z\rangle})/\sigma$ time, implying that $\Delta^{\langle z\rangle}\geq\Omega(n+\Phi^{\langle z\rangle}-\Delta^{\langle z% \rangle})/\sigma$ , resulting in $\Delta^{\langle z\rangle}\in\Omega_{\sigma}(n+\Phi^{\langle z\rangle})$ . $\hfill\blacktriangleleft$

[bib.bib1] [1] A. Acharya and D. M. Mount. Optimally tracking labels on an evolving tree. In Proc. 34th Canad. Conf. Comput. Geom., pages 1–8, 2022.

[bib.bib2] [2] A. Anagnostopoulos, R. Kumar, M. Mahdian, and E. Upfal. Sorting and selection on dynamic data. Theoretical Computer Science, 412(24):2564–2576, 2011. doi:10.1016/j.tcs.2010.10.003.

[bib.bib3] [3] A. Anagnostopoulos, R. Kumar, M. Mahdian, E. Upfal, and F. Vandin. Algorithms on evolving graphs. In Proc. 3rd Innov. Theor. Comput. Sci. Conf., pages 149–160, 2012. doi:10.1145/2090236.2090249.

[bib.bib4] [4] M. Beermann and A. Sieben. The connection between stress, density, and speed in crowds. Scientific Reports, 13:13626, 2023. doi:10.1038/s41598-023-39006-8.

[bib.bib5] [5] J. J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson. Optimally sorting evolving data. In 45th Internat. Colloq. Autom., Lang., and Prog., pages 81:1–81:13, 2018. doi:10.4230/LIPIcs.ICALP.2018.81.

[bib.bib6] [6] J. J. Besa, W. E. Devanny, D. Eppstein, M. T. Goodrich, and T. Johnson. Quadratic time algorithms appear to be optimal for sorting evolving data. In Proc. 20th Workshop Algorithm Eng. and Exp., pages 87–96, 2018.

[bib.bib7] [7] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, 2005.

[bib.bib8] [8] K. Buchin, M. Löffler, P. Morin, and W. Mulzer. Delaunay triangulation of imprecise points simplified and extended. Algorithmica, 61:674–693, 2011. doi:10.1007/s00453-010-9430-0.

[bib.bib9] [9] D. Busto, W. Evans, and D. Kirkpatrick. Minimizing interference potential among moving entities. In Proc. 30th Annu. ACM-SIAM Sympos. Discrete Algorithms, pages 2400–2418, 2019. doi:10.5555/3310435.3310582.

[bib.bib10] [10] T. M. Cover and J. A. Thomas. Elements of Information Theory. Wiley, 2012. doi:10.1002/047174882X.

[bib.bib11] [11] Y. Dodge. The Oxford Dictionary of Statistical Terms. Oxford Univ. Press, 2003. doi:10.1002/sim.1812.

[bib.bib12] [12] W. Evans and D. Kirkpatrick. Minimizing query frequency to bound congestion potential for moving entities at a fixed target time. Algorithms, 17:246, 2024. doi:10.3390/a17060246.

[bib.bib13] [13] J. Gudmundsson, P. Laube, and T. Wolle. Computational movement analysis. In W. Kresse and D. Danko, editors, Handbook of Geogr. Inf., pages 725–741. Springer, 2012. doi:10.1007/978-3-540-72680-7_22.

[bib.bib14] [14] L. J. Guibas, D. Salesin, and J. Stolfi. Epsilon geometry: Building robust algorithms from imprecise computations. In Proc. Fifth Annu. Sympos. Comput. Geom., pages 208–217, 1989. doi:10.1145/73833.73857.

[bib.bib15] [15] D. Helbing, L. Buzna, A. Johansson, and T. Werner. Self-organized pedestrian crowd dynamics: Experiments, simulations, and design solutions. Transportation Science, 39:1–24, 2005. doi:10.1287/trsc.1040.0108.

[bib.bib16] [16] O. Hesham and G. Wainer. Context-sensitive personal space for dense crowd simulation. In Proc. Symp. Simulation for Architecture and Urban Design, pages 1–8, 2017. URL: https://dl.acm.org/doi/10.5555/3289787.3289806.

[bib.bib17] [17] Q. Huang, X. Liu, X. Sun, and J. Zhang. Partial sorting problem on evolving data. Algorithmica, 79:960–983, 2017. doi:10.1007/s00453-017-0295-3.

[bib.bib18] [18] D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40:1098–1101, 1952. doi:10.1109/JRPROC.1952.273898.

[bib.bib19] [19] U. Jain. Effects of population density and resources on the feeling of crowding and personal space. J. Social Psych., 127:331–338, 1987. doi:10.1080/00224545.1987.9713699.

[bib.bib20] [20] S. Kahan. A model for data in motion. In Proc. 23rd Annu. ACM Sympos. Theory Comput., pages 265–277, 1991. doi:10.1145/103418.103449.

[bib.bib21] [21] V. Kanade, N. Leonardos, and F. Magniez. Stable matching with evolving preferences. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2016.

[bib.bib22] [22] M. G. Kendall. A new measure of rank correlation. Biometrika, 30:81–93, 1938. doi:10.2307/2332226.

[bib.bib23] [23] S. Kullback and R. A. Leibler. On information and sufficiency. Ann. Math. Statist., 22:79–86, 1951. doi:10.1214/aoms/1177729694.

[bib.bib24] [24] P. Laube. Computational Movement Analysis. Springer Cham, 2014. doi:10.1007/978-3-319-10268-9.

[bib.bib25] [25] M. Löffler and M. van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56:235–269, 2010. doi:10.1007/s00453-008-9174-2.

[bib.bib26] [26] D. J. C. MacKay. Information Theory, Inference and Learning Algorithms. Cambridge University Press, 2003. URL: https://books.google.com/books?id=AKuMj4PN_EMC.

[bib.bib27] [27] F. Nielsen. Statistical divergences between densities of truncated exponential families with nested supports: Duo Bregman and duo Jensen divergences. Entropy, 24:421, 2022. doi:10.3390/e24030421.

[bib.bib28] [28] R. Pan, Z. Han, T. Liu, H. Wang, J. Huang, and W. Wang. An RFID tag movement trajectory tracking method based on multiple RF characteristics for electronic vehicle identification ITS applications. Sensors, 23:7001, 2023. doi:10.3390/s23157001.

[bib.bib29] [29] A. Seyfried, B. Steffen, W. Klingsch, and M. Boltes. The fundamental diagram of pedestrian movement revisited. J. Stat. Mech. Theory Exp., 2005:P10002, 2005. doi:10.1088/1742-5468/2005/10/P10002.

[bib.bib30] [30] C. E. Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27:623–656, 1948. doi:10.1002/j.1538-7305.1948.tb00917.x.

[bib.bib31] [31] S. M. Tomkiewicz, M. R. Fuller, J. G. Kie, and K. K. Bates. Global positioning system and associated technologies in animal behaviour and ecological research. Phil. Trans. R. Soc. B, 365:2163–2176, 2010. doi:10.1098/rstb.2010.0090.

[bib.bib32] [32] M. van Kreveld, M. Löffler, F. Staals, and L. Wiratma. A refined definition for groups of moving entities and its computation. Internat. J. Comput. Geom. Appl., 28(2):181–196, 2018. doi:10.4230/LIPIcs.ISAAC.2016.130.

[bib.bib33] [33] S. Verdú. The Cauchy distribution in information theory. Entropy, 25:346, 2023. doi:10.3390/e25020346.

[bib.bib34] [34] L. Wiratma, M. Löffler, and F. Staals. An experimental comparison of two definitions for groups of moving entities. In Proc. 10th Internat. Conf. Geogr. Inf. Sci., pages 64:1–64:6, 2018. doi:10.4230/LIPIcs.GIScience.2018.64.

[bib.bib35] [35] S. Yi, H. Li, and X. Wang. Understanding pedestrian behaviors from stationary crowd groups. In Proc. IEEE Conf. Comput. Vis. Pattern Recogn., pages 3488–3496, 2015. doi:10.1109/CVPR.2015.7298971.

[bib.bib36] [36] Y. Zou, G. Zeng, Y. Wang, X. Liu, X. Sun, J. Zhang, and Q. Li. Shortest paths on evolving graphs. In H. T. Nguyen and V. Snasel, editors, Computational Social Networks, pages 1–13. Springer, 2016. doi:10.1007/978-3-319-42345-6_1.

Evolving Distributions Under Local Motion

Abstract

Keywords and phrases:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

Acknowledgements:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

2 Problem Formulation and Results

Objects

The Local-Motion Model

Oracle

Hypotheses and Distance

Class of Algorithms

Objective and Results

Theorem 1.

Why the KL Divergence?

Paper Organization

3 Lower Bound

Theorem 2.

4 Algorithm

4.1 Potential Function

Lemma 3.

Proof.

▶ Remark (Potential function and approximating pairwise distances).

Lemma 4.

4.2 The Algorithm

4.3 Analysis

Lemma 5 (Expansion Factor).

Lemma 6 (Algorithm’s contribution towards Φ).

Lemma 7 (Iteration time proportional to Potential).

Lemma 8.

Proof.

Corollary 9.

5 Extensions and Conclusion

References

Appendix A Appendix

A.1 Deferred Proofs

Lemma 10 (Done tracking Xi).

Proof.

Theorem 2 (Lower Bound on the Distance).

Proof.

Lemma 11 (Evolver’s contribution to Φ).

Proof.

Lemma 12 (Algorithm’s contribution towards Φ).

Proof.

Lemma 13 (Iteration time proportional to Potential).

Proof.

$\blacktriangleright$ Remark (Potential function and approximating pairwise distances).

Lemma 6 (Algorithm’s contribution towards $\Phi$ ).

Lemma 10 (Done tracking $X_{i}$ ).

Lemma 11 (Evolver’s contribution to $\Phi$ ).

Lemma 12 (Algorithm’s contribution towards $\Phi$ ).