Department of Computer Science and Software Engineering,
Penn State Erie, The Behrend College, Erie, United<EMAIL_ADDRESS>Department of Computer Science and Engineering,
State University of New York at Buffalo, Buffalo, United
<EMAIL_ADDRESS>research of this author was supported in part by
NSF through grant IIS-1910492 and by KAUST through grant CRG10 4663.2. Ziyun
Huang and Jinhui Xu [100]Theory of Computation Computational Geometry 0 2022

# In-Range Farthest Point Queries and Related Problem in High Dimensions

Ziyun Huang  Jinhui Xu

###### Abstract

Range-aggregate query is an important type of queries with numerous
applications. It aims to obtain some structural information (defined by an
_aggregate function_ $F(\cdot)$) of the points (from a point set $P$) inside a
given query range $B$. In this paper, we study the range-aggregate query
problem in high dimensional space for two aggregate functions: (1) $F(P\cap
B)$ is the farthest point in $P\cap B$ to a query point $q$ in
$\mathbb{R}^{d}$ and (2) $F(P\cap B)$ is the minimum enclosing ball (MEB) of
$P\cap B$. For problem (1), called _In-Range Farthest Point (IFP) Query_ , we
develop a bi-criteria approximation scheme: For any $\epsilon>0$ that
specifies the approximation ratio of the farthest distance and any $\gamma>0$
that measures the “fuzziness” of the query range, we show that it is possible
to pre-process $P$ into a data structure of size
$\tilde{O}_{\epsilon,\gamma}(dn^{1+\rho})$ in
$\tilde{O}_{\epsilon,\gamma}(dn^{1+\rho})$ time such that given any
$\mathbb{R}^{d}$ query ball $B$ and query point $q$, it outputs in
$\tilde{O}_{\epsilon,\gamma}(dn^{\rho})$ time a point $p$ that is a
$(1-\epsilon)$-approximation of the farthest point to $q$ among all points
lying in a $(1+\gamma)$-expansion $B(1+\gamma)$ of $B$, where $0<\rho<1$ is a
constant depending on $\epsilon$ and $\gamma$ and the hidden constants in
big-O notations depend only on $\epsilon$, $\gamma$ and $\text{Polylog}(nd)$.
For problem (2), we show that the IFP result can be applied to develop query
scheme with similar time and space complexities to achieve a
$(1+\epsilon)$-approximation for MEB. To the best of our knowledge, these are
the first theoretical results on such high dimensional range-aggregate query
problems. Our results are based on several new techniques, such as multi-scale
construction and ball difference range query, which are interesting in their
own rights and could be potentially used to solve other range-aggregate
problems in high dimensional space.

###### keywords:

Farthest Point Query, Range Aggregate Query, Minimum Enclosing Ball,
Approximation, High Dimensional Space

##  1 Introduction

Range search is a fundamental problem in computational geometry and finds
applications in many fields like database systems and data mining [1, 2]. It
has the following basic form: Given a set of $n$ points $P$ in
$\mathbb{R}^{d}$, pre-process $P$ into a data structure so that for any query
range $B$ from a certain range family (_e.g.,_ spheres, rectangles, and
halfspaces), it reports or counts the number of the points in $P\cap B$
efficiently. Range search allows us to obtain some basic information of the
points that lie in a specific local region of the space.

In many applications, it is often expected to know more information than
simply the number of points in the range. This leads to the study of range-
aggregate query [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13], which is a relatively
new type of range search. The goal of range-aggregate query is to obtain more
complicated structural information (such as the diameter, the minimum
enclosing ball, and the minimum spanning tree) of the points in the query
range. Range-aggregate query can be generally defined as follows: Given a
point set $P$, pre-process $P$ into a data structure such that for any range
$B$ in a specific family, it outputs $F(P\cap B)$, where $F(\cdot)$ is a given
_aggregate function_ that computes a certain type of information or structure
of $P\cap B$ like “diameter”,“minimum enclosing ball”, and “minimum spanning
tree”. Range-aggregate queries have some interesting applications in data
analytics and big data [14, 15, 16, 13], where it is often required to
retrieve aggregate information of the records in a dataset with keys that lie
in any given (possibly high dimensional) range.

In this paper, we study the range-aggregate query problem in high dimensions
for spherical ranges. Particularly, we consider two aggregate functions for
any $\mathbb{R}^{d}$ query ball $B$: (1) $F(P\cap B)$ is the farthest point in
$P\cap B$ to a query point $q$ in $\mathbb{R}^{d}$ and (2) $F(P\cap B)$ is the
minimum enclosing ball (MEB) of $P\cap B$. We will focus in this paper on
problem (1), called the _In-Range Farthest Point (IFP) Query_ , and show that
an efficient solution to IFP query also yields efficient solutions to the MEB
problems. We start with some definitions.

######  Definition 1.1.

(Approximate IFP (AIFP)) Let $P$ be a set of $n$ points in $\mathbb{R}^{d}$,
$q$ be a point and $B$ be a $d$-dimensional (closed) ball. A point $p\in P$ is
a bi-criteria $(\epsilon,\gamma)$-approximate in-range farthest point (or
AIFP) of $q\in P$ in $B$, if there exists a point set $P^{\prime}$ such that
the following holds, where $\epsilon$ and $\gamma$ are small positive
constants, and $B(1+\gamma)$ is the ball concentric with $B$ and with radius
$(1+\gamma)r$: (1) $P\cap B\subseteq P^{\prime}\subseteq P\cap B(1+\gamma)$;
(2) $p\in P^{\prime}$; and (3) for any $p^{\prime}\in P^{\prime}$,
$(1-\epsilon)\lVert p^{\prime}-q\rVert\leq\lVert p-q\rVert$.

Defining AIFP in this way enables us to consider all points in $B$ and exclude
all points outside of $B(1+\gamma)$. Points in the fuzzy region
$B(1+\gamma)\setminus B$ may or may not be included in the farthest point
query. Note that allowing fuzzy region is a commonly used strategy to deal
with the challenges in many high dimensional similarity search and range query
problems. For example, consider the classic near neighbor search problem,
which is equivalent to spherical emptiness range search: Given a query sphere
$B$ in $\mathbb{R}^{d}$, report a data point $p$ that lies in $B$ if such a
data point exists. In high dimensional space, obtaining an exact solution to
such a query is very difficult. A commonly used technique for this problem is
the Locality Sensitive Hashing (LSH) scheme [17]. Given a query ball $B$, LSH
could report a data point in $B(1+\epsilon)$ for some given factor
$\epsilon>0$. In other words, a fuzzy region $B(1+\epsilon)\setminus B$ is
allowed. Similarly, we can define approximate MEB for points in a given range
with a fuzzy region.

######  Definition 1.2.

(Minimum Enclosing Ball (MEB)) Let $P$ be a set of $n$ points in
$\mathbb{R}^{d}$. A $d$-dimensional (closed) ball $B$ is an enclosing ball of
$P$ if $P\subset B$ and $B$ is the minimum enclosing ball (MEB) of $P$ if its
radius $r$ is the smallest among all enclosing balls. A ball $B^{\prime}$ is a
$(1+\epsilon)$-approximate MEB of $P$ for some constant $\epsilon>0$ if it is
an enclosing ball of $P$ and its radius is no larger than
$(1+\epsilon)Rad(P)$, where $Rad(P)$ is the radius of the MEB of $P$.

######  Definition 1.3.

(Approximate MEB (AMEB)) Let $P$ be a set of $n$ points and $B$ be any ball
with radius $r$ in $\mathbb{R}^{d}$. A ball $B^{\prime}$ with radius
$r^{\prime}$ is a bi-criteria $(\epsilon,\gamma)$-approximate MEB (or AMEB) of
$P$ in range $B$, if there exists a point set $P^{\prime}$ such that the
following holds, where $\gamma$ and $\epsilon$ are small positive constants:
(1) $P\cap B\subseteq P^{\prime}\subseteq P\cap B(1+\gamma)$; and (2)
$B^{\prime}$ is a $(1+\epsilon)$-approximate MEB of $P^{\prime}$.

In this paper, we will focus on building a data structure for $P$ so that
given any query ball $B$ and a point $q\in\mathbb{R}^{d}$, an AIFP of $q$ in
$P\cap B$ can be computed efficiently (i.e., in sub-linear time in terms of
$n$). Below are the main theorems of this paper. Let $\epsilon>0,\gamma>0$,
$0<\delta<1$ be any real numbers.

######  Theorem 1.4.

For any set $P$ of $n$ points in $\mathbb{R}^{d}$, it is possible to build a
data structure of size
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\text{Polylog}(nd))$ in
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\text{Polylog}(nd))$ pre-
processing time, where $0<\rho<1$ is a small constant depending on $\epsilon$
and $\gamma$. With this data structure, it is then possible to find a
$(\epsilon,\gamma)$-AIFP of any given query point $q$ and query ball $B$ in
$O_{\epsilon,\gamma}(dn^{\rho}\log\delta^{-1}\text{Polylog}(nd))$ time with
probability at least $1-\delta$.

Note: In the above result, the relationship between $\rho$ and
$\epsilon,\gamma$ has a rather complicated dependence on several constants of
$p$-stable distribution, which is inherited from the underlying technique of
Locality Sensitive Hashing (LSH) scheme [17]. This indicates that for any
$\epsilon,\gamma$, we have $0<\rho<1$ and $\rho$ approaches $1$ as
$\epsilon,\gamma$ approach $0$.

We will also show how to use the AIFP data structure to answer MEB queries
efficiently.

######  Theorem 1.5.

For any set $P$ of $n$ points in $\mathbb{R}^{d}$, it is possible to build a
data structure of size
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\text{Polylog}(nd))$ in
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\text{Polylog}(nd))$ pre-
processing time, where $0<\rho<1$ is a small constant depending on $\epsilon$
and $\gamma$. With this data structure, it is then possible to find a
$(\epsilon,\gamma)$-AMEB for any query ball $B$ in
$O_{\epsilon,\gamma}(dn^{\rho}\log\delta^{-1}\text{Polylog}(nd))$ time with
probability at least $1-\delta$.

To our best knowledge, these are the first results on such range-aggregate
problems in high dimensions. Each data structure has only a near linear
dependence on $d$, a sub-quadratic dependence on $n$ in space complexity, and
a sub-linear dependence on $n$ in query time.

Our Method: The main result on AIFP is based on several novel techniques, such
as multi-scale construction and ball difference range query. Briefly speaking,
multi-scale construction is a general technique that allow us to break the
task of building an AIFP query data structure into a number of “constrained”
data structures. Each such data structure is capable of correctly answering an
AIFP query given that some assumption about the query holds (for example, the
distance from $q$ to its IFP is within a certain range). Multi-scale
construction uses a number of “constrained” data structures of small size to
cover all possible cases of a query, which leads to a data structure that can
handle any arbitrary queries. Multi-scale construction is independent of the
aggregate function, and thus has the potential be used as a general method for
other types of range-aggregate query problems in high dimensional space.
Another important technique is a data structure for the ball difference range
query problem, which returns a point, if there is one, in the difference of
two given query balls. The ball difference data structure is the building
block for the constrained AIFP data structures, and is interesting in its own
right as a new high dimensional range search problem.

Related Work: There are many results for the ordinary farthest point query
problem in high dimensional space [18, 19, 20, 21]. However, to the best of
our knowledge, none of them is sufficient to solve the IFP problem, and our
result is the first one to consider the farthest point problem under the query
setting. Our technique for the IFP problem also yields solutions to other
range-aggregate queries problems, including the MEB query problem.

A number of results exist for various types of the range-aggregate query
problem in fixed dimensional space. In [5], Arya, Mount, and Park proposed an
elegant scheme for querying minimum spanning tree inside a query range. They
showed that there exists a bi-criteria
$(\epsilon_{q},\epsilon_{w})$-approximation with a query time of $O(\log
n+(1/\epsilon_{q}\epsilon_{w})^{d})$. In [10], Nekrich and Smid introduced a
data structure to compute an $\epsilon$-coreset for the case of orthogonal
query ranges and aggregate functions satisfying some special properties. Xue
[22] considered the colored closest-pair problem in a (rectangular) range and
obtained a couple of data structures with near linear size and polylogarithmic
query time. Recently, Xue _et. al._ [23] further studied more general versions
of the closest-pair problem and achieved similar results. For the MEB problem
under the range-aggregate settings, Brass et al. are the first to investigate
the problem in 2D space, along with other types of aggregate functions (like
width and the size of convex hull) [6]. They showed that it is possible to
build a data structure with $O(n\cdot polylog(n))$ pre-processing space/time
and $O(polylog(n))$ query time.

All the aforementioned methods were designed for fixed dimensional space, and
thus are not applicable to high dimensions. Actually, range aggregation has
rarely been considered in high dimensions, except for a few results that may
be viewed as loosely relevant. For example, Abbar et al. [24] studied the
problem of finding the maximum diverse set for points inside a ball with fixed
radius around a query point. Their ideas are seemingly useful to our problem.
However, since their ball always has the same fixed radius, their techniques
are not directly applicable. In fact, a main technical challenge of our
problem is how to deal with the arbitrary radius and location of the query
range, which is overcome by our multi-scale construction framework. Another
related work by Aumüller _et. al._ [25] has focused on random sampling in a
given range. The technique is also not directly applicable to IFP.

###  1.1 Overviews of the Main Ideas

Below we describe the main ideas of our approaches. For simplicity, in the
following we ignore the fuzziness of the query range. We approach the AIFP
query problem by first looking at an easier version: given ball $B$ and point
$q$, find an approximate farthest point in $P\cap B$ to $q$, with the (strong)
assumption that the radius of $B$ is a fixed constant $r_{B}>0$, and that the
distance between $q$ and its IFP in $P\cap B$ is within a range of
$(d_{min},d_{max}]$, where $d_{max}>d_{min}>0$ are fixed constants. We call
such a problem a constrained AIFP problem. We use a tuple
$(r_{B},d_{min},d_{max})$ to denote such a constraint.

To solve the constrained AIFP problem, we develop a data structure for the
_ball difference (BD) range query_ problem, which is defined as follows: given
two balls $B_{in}$ and $B_{out}$, find a point that lies in $P\cap
B_{in}\setminus B_{out}$. With such a data structure, it is possible to reduce
an AIFP query with constraint $(r_{B},d_{min},d_{max})$ to a series of BD
queries. Below we briefly describe the idea. Let $r_{0}=d_{min}$, and for
$i=1,2,3\ldots$, let $r_{i}=(1+\epsilon)r_{i-1}$, where $\epsilon>0$ is an
approximation factor. For $i=0,1,\ldots$, we try to determine whether there is
a point in $P\cap B$ whose distance to $q$ is larger than $r_{i}$. Note that
this can be achieved by a BD query with $B_{in}:=B$ and $B_{out}$ being the
ball centered at $q$ and with radius $r_{i}$. By iteratively doing this,
eventually we will reach an index $j$ such that it is possible to find a point
$p\in B\cap P$ that satisfies the condition of $\lVert p-q\rVert>r_{j}$, but
no point lies in $P\cap B$ whose distance to $q$ is larger than
$r_{j+1}=(1+\epsilon)r_{j}$. Thus, $p$ is a $(1-O(\epsilon))$-approximate
farthest point to $q$ in $P\cap B$. From the definition of constrained AIFP
query, it is not hard to see that this process finds the AIFP after at most
$O(\log_{1+\epsilon}\frac{d_{max}}{d_{min}})$ iterations. Every BD data
structure supports only $B_{in}$ and $B_{out}$ with fixed radii. This means
that we need to build $O(\log_{1+\epsilon}\frac{d_{max}}{d_{min}})$ BD data
structures for answering any AIFP query with constraint
$(r_{B},d_{min},d_{max})$.

With the constrained AIFP data structure, we then extend it to a data
structure for answering general AIFP queries. Our main idea is to use the
aforementioned multi-scale construction technique to build a collection of
constrained data structures, which can effectively cover (almost) all possible
cases of the radius of $B$ and the farthest distance from $q$ to any point in
$B\cap P$. More specifically, for any AIFP query, it is always possible to
either answer the query easily without using any constrained data structures,
or find a constrained data structure such that the AIFP query satisfies the
constraint $(r_{B},d_{min},d_{max})$, and thus can be used to answer the AIFP
query.

For AMEB query, we follow the main idea of Badoiu and Clarkson [26], and show
that an AMEB query is reducible to a sequence of AIFP queries. More
discussions are left to Section 5.

##  2 Constrained AIFP Query

In this section, we discuss how to construct a data structure to answer
constrained AIFP queries. Particularly, given any ball $B$ and point $q$
satisfying the constraint $(r_{B},d_{min},d_{max})$,

  * •

the radius of $B$ is $r_{B}$,

  * •

the distance from $q$ to its farthest point to $P\cap B$ is within the range
of $(d_{min},d_{max}]$,

the data structure can find the AIFP to $q$ in $P\cap B$ in sub-linear time
(with high probability).

In the following, we let $\epsilon>0$ be an approximation factor, $\gamma>0$
be a factor that controls the region fuzziness and $0<\delta<1$ be a factor
controlling the query success probability. The main result of this section is
summarized as the following lemma.

######  Lemma 2.1.

Let $P$ be a set of $n$ points in $\mathbb{R}^{d}$. It is possible to build a
data structure for $P$ with size
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\log(d_{max}/d_{min}))$ in
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1}\log(d_{max}/d_{min}))$ time,
where $0<\rho<1$ is a real number depending on $\epsilon$ and $\gamma$, and
the constants hidden in the big-O notation depend only on $\epsilon,\gamma$.
Given any query $(B,q)$ that satisfies the constraint of
$(r_{B},d_{min},d_{max})$, with probability at least $1-\delta$, the data
structure finds an $(\epsilon,\gamma)$-AIFP for $q$ in $P\cap B$ within time
$O_{\epsilon,\gamma}(dn^{\rho}\log\delta^{-1}\log(d_{max}/d_{min}))$.

In the following, we consider an AIFP query that satisfies constraint
$(r_{B},d_{min},d_{max})$. As mentioned in last section, it is possible to
reduce a constrained AIFP query to a series of _ball difference(BD) range
queries_ , which report a point in $P$ that lies (approximately) in
$B_{in}\setminus B_{out}$ for a given pair of $\mathbb{R}^{d}$ balls $(B_{in}$
and $B_{out})$, or return NULL if no such point exists. Below, we describe the
reduction using a ball-peeling strategy. We consider a series of balls
$B_{0},B_{1},B_{2},\ldots$ concentric at $q$ with an exponentially increasing
radius. Let $\xi>0$ be a to-be-determined approximation factor, and
$B_{0}:=\mathcal{B}(q,d_{min})$ which is the ball centered at $q$ with radius
$d_{min}$. For integer $i>0$, let $B_{i+1}=B_{i}(1+\xi)$ which is the ball
obtained by enlarging the radius of $B_{i}$ by a factor of $(1+\xi)$.
111Throughout this paper we use similar notations. Let $q$ be any point and
$x>0$ be real number. Then, $\mathcal{B}(q,x)$ denotes the ball centered at
$q$ and with radius $x$. Let $B$ be any ball. For real number $y>0$, we let
$B(y)$ denote the ball obtained by enlarging (or shrinking if $y<1$) the
radius of $B$ by a factor of $y$. For $i=0,1,2,\ldots$, repeatedly perform a
BD query with $B_{in}:=B$ and $B_{out}:=B_{i}$, until an index $j$ is
encountered such that the BD query reports a point $p_{j}$ that lies in $P\cap
B\setminus B_{j}$, but returns NULL when trying to find a point in $P\cap
B\setminus B_{j+1}$. If $\xi$ is a small enough constant, it is not hard to
see that $p_{j}$ is a good approximation of the IFP to $q$ in $P\cap B$. Note
that in this process, no more than $\log_{1+\xi}(d_{max}/d_{min})$ BD queries
are required. This is because the distance between $q$ and any point in $B$ is
at most $d_{max}$. Thus, it is not necessary to increase the radius of
$B_{out}$ to be more than $d_{max}$ in the BD range query. The bound on the
number of BD range queries then follows from the facts that the series of BD
range queries starts with a $B_{out}$ ball of radius $d_{min}$ and each time
the radius of $B_{out}$ is increased by a factor of $1+\xi$. This process is
similar to peel a constant portion of $B_{in}$ each time by $B_{out}$. See
Figure 1 for an illustration.

Figure 1: An illustration of answering a constrained AIFP query using BD
queries.

The above discussion suggests that a constrained AIFP data structure can be
built through (approximate) BD query data structures, which have the following
definition. Let $\xi>0$ be an approximation factor. A data structure is called
$\xi$-error BD for a point set $P$, if given any balls $B_{in}$ and $B_{out}$,
it answers the following query (with high success probability):

  1. 1.

If there exists a point in $P\cap(B_{in}\setminus B_{out})$, the data
structure returns a point in $P\cap(B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1}))$.

  2. 2.

Otherwise, it returns a point in $P\cap(B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1}))$ or NULL.

The details of how to construct a $\xi$-error BD data structure is left to the
next subsection. Below is the main result of the BD query data structure for
$\xi>0$, fixed constant $r_{in}>0,r_{out}>0$ and success probability
controlling factor $0<\delta<1$.

######  Lemma 2.2.

It is possible to build a $\xi$-error BD query data structure of size
$O_{\xi}(dn^{1+\rho}\log\delta^{-1})$ in $O_{\xi}(dn^{1+\rho}\log\delta^{-1})$
time, where $0<\rho<1$ depends only on $\xi$. The query time of this data
structure is $O_{\xi}(dn^{\rho}\log\delta^{-1})$. For any pair of query balls
$B_{in}$ and $B_{out}$ with radius $r_{in}$ and $r_{out}$, respectively, the
data structure answers the query with success probability at least $1-\delta$.

Note that each BD query data structure works only for query balls $B_{in}$ and
$B_{out}$ with fixed radii $r_{in}$ and $r_{out}$, respectively. This means
that the constrained AIFP data structure should consist of multiple BD data
structures with different values of $r_{in}$ and $r_{out}$.

From the above discussion, we know that a constrained AIFP data structure can
be built by constructing a sequence of $\log(d_{max}/d_{min})$ BD data
sturctures with $r_{in}:=r_{B}$ and $r_{out}$ being
$d_{min},(1+\xi)d_{min},(1+\xi)^{2}d_{min},\ldots$. Such a data structure will
allow us to answer constrained AIFP queries using the ball peeling strategy.

Given any constants $\epsilon>0$, $\gamma>0$, $0<\delta<1$, and constraint
$(r_{B},d_{min},d_{max})$, the following Algorithm 1 builds a constrained AIFP
data structure for a given point set $P$. The data structure is simply a
collection of BD query data structures.

Algorithm 1 Build-CAIFP$(P;\epsilon,\gamma,\delta;r_{B},d_{min},d_{max})$

Input: A $\mathbb{R}^{d}$ point set $P$ with cardinality $n$. Constants
$\epsilon>0,\gamma>0,0<\delta<1$. Constraint tuple $(r_{B},d_{min},d_{max})$.
Output: A number of BD-Query data structures built with different parameters.

1: Let $\xi=\min\\{(1-\epsilon)^{-1/2}-1,\gamma\\}$. Construct a sequence of
real numbers $r_{0},r_{1},r_{2},\ldots,r_{m}$, by letting $r_{0}=d_{min}$, $m$
be the integer such that $r_{0}(1+\xi)^{m-1}<d_{max}$ and
$r_{0}(1+\xi)^{m}\geq d_{max}$, $r_{i}=(1+\xi)r_{i-1}$ for $i=1,2,\ldots,m$,
and $\delta^{\prime}=\delta/m$.

2: FOR $i=0,1,2,\ldots,m$, build a $\xi$-error BD query data structure for
query balls with radii $r_{in}=r_{B}$ and $r_{out}=r_{i}$, with query success
probability at least $1-\delta^{\prime}$.

With such a collection of BD query data structures, we can answer any
constrained AIFP query satisfying $(r_{B},d_{min},d_{max})$ by applying the
ball peeling strategy mentioned before. The algorithm is formally described as
the Algorithm 2 below.

Algorithm 2 Query-CAIFP$(B,q)$

Input: A constrained AIFP query $(B,q)$ with constraint
$(r_{B},d_{min},d_{max})$.
Output: A point $p_{ans}$ that is an approximate farthest point in $B\cap Q$
to $p$, or NULL if no such point exists.

1: Initialize variable $p_{ans}$ $\leftarrow$ NULL. Note: In the following, we
use $m$ and $r_{i}$ for $i=0,1,\ldots,m$ as in Algorithm 1.

2: For $i$ from $0$ to $m$: Make a query $(B,B_{out,i})$ to the BD-Query data
structure $BD_{i}$, by letting $B_{out,i}:=\mathcal{B}(q,r_{i})$. If the query
answer is NULL, Return $p_{ans}$. Otherwise update $p_{ans}$ to be the query
answer.

3:Return $p_{ans}$.

By some simple calculation, we know that the probability that all the BD
queries in Algorithm 2 are successful is at least $1-\delta$, and when this
happens, the output point $p_{ans}$ is an $(\epsilon,\gamma)$-AIFP of $q$ in
$B\cap P$. This is summarized as the following lemma.

######  Lemma 2.3.

With probability at least $1-\delta$, Algorithm 2 outputs a point $p_{ans}\in
B(1+\gamma)$ such that for any $q\in B\cap P$, $\lVert
p_{ans}-p\rVert\geq(1-\epsilon)\lVert q-p\rVert$.

Next we analyze the space/time complexity of the AIFP scheme. The query data
structure is a combination of $m=O_{\epsilon,\gamma}(\log(d_{max}/d_{min}))$
BD data structures. From the discussion of BD data structures (see Lemma 2.2),
every BD query data structure we build has space/time complexity
$O_{\epsilon,\gamma}(dn^{1+\rho}\log\delta^{-1})$ where $0<\rho<1$ depends
only on $\epsilon,\gamma$. Each BD query takes
$O_{\epsilon,\gamma}(dn^{\rho}\log\delta^{-1})$ time. Lemma 2.1 then follows.

###  2.1 The BD Query Scheme

In this subsection we present the BD query scheme. To our best knowledge, this
is the first theoretical result to consider the BD range search problem. A
very special case of BD query called the “annulus queries” where the two balls
are co-centered is studied in [27]. Nonetheless, the technique is not directly
applicable to general BD queries. Our BD range query scheme is based on the
classic Locality Sensitive Hashing (LSH) technique [28, 29, 17] which has been
a somewhat standard technique for solving the proximity problems in high
dimensional space. The main idea of LSH is to utilize a family of hash
functions (called an LSH family) that have some interesting properties. Given
two points $p$ and $q$ in $\mathbb{R}^{d}$, if we randomly pick a function $h$
from the LSH family, the probability that the event of $h(p)=h(q)$ happens
will be high if $\lVert p-q\rVert$ is smaller than a threshold value, and the
probability for the same event will be lower if $\lVert p-q\rVert$ is larger.
Such a property of the LSH family allows us to develop hashing and bucketing
based schemes to solve similarity search problems in high dimensional space.
Below is the definition of an LSH family.

######  Definition 2.4.

Let $0<r_{1}<r_{2}$ and $1>\mathsf{P}_{1}>\mathsf{P}_{2}>0$ be any real
numbers. A family $\mathcal{H}=\\{h:\mathbb{R}^{d}\rightarrow U\\}$, where $U$
can be any set of objects, is called
$(r_{1},r_{2},\mathsf{P}_{1},\mathsf{P}_{2})$-sensitive, if for any
$p,q\in\mathbb{R}^{d}$.

  1. 1.

if $\lVert p-q\rVert\leq r_{1}$, then
$\text{Pr}_{\mathcal{H}}[h(p)=h(q)]\geq\mathsf{P}_{1}$,

  2. 2.

if $\lVert p-q\rVert>r_{2}$, then
$\text{Pr}_{\mathcal{H}}[h(p)=h(q)]\leq\mathsf{P}_{2}$.

It was shown in [17] that for any dimension $d$ and any $r>0,c>1$, an
$(r,cr,\mathsf{P}_{1},\mathsf{P}_{2})$-sensitive family $\mathcal{H}$ exists,
where $1>\mathsf{P}_{1}>\mathsf{P}_{2}>0$ depends only on $c$. Every hash
function $h(p):\mathbb{R}^{d}\rightarrow\mathbb{Z}$ maps a point $p$ in
$\mathbb{R}^{d}$ to an integer, and $h(p)$ has the form
$h(p)=\lfloor\frac{a\cdot p+b}{r}\rfloor$ for some $\mathbb{R}^{d}$ vector $a$
and integers $b,r$. It takes $O(d)$ time to sample a hash function $h$ from
such a family and compute $h(p)$. Our data structure will make use of two such
families. Let $\mathcal{H}_{in}$ be an
$(r_{in},(1+\xi)r_{in},\mathsf{P}_{1},\mathsf{P}_{2})$-sensitive family, and
$\mathcal{H}_{out}$ be a $((1+\xi)^{-1}r_{out},r_{out},\mathsf{P}_{1}$,
$\mathsf{P}_{2})$-sensitive family, where $0<\mathsf{P}_{1},\mathsf{P}_{2}<1$
are constants depending only on $\xi$, as described in [17]. Given any BD-
query $(B_{in},B_{out})$ with the centers of the balls being $o_{in},o_{out}$
respectively, the family $\mathcal{H}_{in}$ helps us to identify points that
are close enough to $o_{in}$ (and therefore lie in $B_{in}$), and
$\mathcal{H}_{out}$ helps us to identify points that are far away enough from
$o_{out}$ (and therefore lie outside of $B_{out}$).

High level idea: Our approach is based on a novel bucketing and query scheme
that utilizes the properties of the LSH family. Before presenting the
technical details, We first illustrate the high level idea. For convenience,
we assume for now that the functions in $\mathcal{H}_{in}$ and
$\mathcal{H}_{out}$ have range $\\{0,1\\}$ (this is achievable by some simple
modification to these hash function families). We use a randomized process to
create a hybrid random hash function $S(\cdot)$ that maps any point in
$\mathbb{R}^{d}$ to a bit string. Such a function $S(\cdot)$ is a
concatenation of a number of hash functions drawn from $\mathcal{H}_{in}$ and
$\mathcal{H}_{out}$. Given $p\in\mathbb{R}^{d}$, $S(\cdot)$ applies the
aforementioned hash functions (drawn from $\mathcal{H}_{in}$ and
$\mathcal{H}_{out}$) on $p$ to obtain a bit-string. With such a function
$S(\cdot)$, consider comparing the bit-strings of $S(p),S(q)$ for points
$p,q\in\mathbb{R}$. Intuitively, based on the properties of $\mathcal{H}_{in}$
and $\mathcal{H}_{out}$, we know that if $p,q$ are close enough, $S(p)$ and
$S(q)$ should have many common bits in positions that are determined by
functions from $\mathcal{H}_{in}$. Contrarily, if $p,q$ are far away, $S(p)$
and $S(q)$ should have only a few common bits in positions that are determined
by functions from $\mathcal{H}_{out}$.

For every point $p\in P$, we use $S(p)$ to compute a bit-string label for $p$,
and put $p$ into the corresponding buckets (i.e., labeled with the same bit-
strings). To answer a given BD query $B_{in},B_{out}$ with centers of the
balls being $o_{in},o_{out}$, respectively, we compute $S(o_{in})$ and
$S(o_{out})$. Note that, based on the above discussion, we know that if a
point $p$ satisfies the condition of $p\in B_{in}\setminus B_{out}$, then
$S(p)$ and $S(o_{in})$ should have many common bits in the positions
determined by $\mathcal{H}_{in}$, and $S(p)$ and $S(o_{out})$ should have few
common bits in the positions determined by $\mathcal{H}_{out}$. Thus, by
counting the number of common bits in the labels, we can then locate buckets
that are likely to contain points close to $o_{in}$ and far away from
$o_{out}$, _i.e.,_ points are likely to be in $B_{in}\setminus B_{out}$. To
achieve the desired outcome, we will create multiple set of buckets using
multiple random functions $S(p)$.

Details of the Algorithms: After understanding the above general idea, we now
present the data structure and the query algorithm along with the analysis.
Let
$\mathsf{P}^{\prime}_{1}=(1+\mathsf{P}_{1})/2,\mathsf{P}^{\prime}_{2}=(1+\mathsf{P}_{2})/2,\eta=(\mathsf{P}^{\prime}_{1}-\mathsf{P}^{\prime}_{2})/3$,
$a=\lceil(2\mathsf{P}^{\prime}_{1}\ln 3)/\eta^{2}\rceil$.
$\mathsf{P}^{\prime\prime}_{1}=2^{-2a}\cdot 4/9$,
$\mathsf{P}^{\prime\prime}_{2}=2^{-2a}/3,b=\lceil\log_{1/\mathsf{P}^{\prime\prime}_{2}}n\rceil$,
$\rho=\frac{\ln 1/\mathsf{P}^{\prime\prime}_{1}}{\ln
1/\mathsf{P}^{\prime\prime}_{2}}$, and $c=\lceil
n^{\rho}/\mathsf{P}^{\prime\prime}_{1}\rceil$. Let $F_{Z}$ be a function that
maps every element in $\mathbb{Z}$ randomly to $0$ or $1$, each with
probability $1/2$. The following Algorithm 3 shows how to construct a
$\xi$-error BD range query data structure for any point set $P$ and radii
$r_{in}$ and $r_{out}$. The data structure consists of $c$ groups of buckets,
each created using a random function $S(p)$ that maps a point to a bit-string
of total length $2ab$.

Algorithm 3 CreateBuckets$(P,\xi,r_{in},r_{out})$

Input: A point set $P$. Parameters $\xi>0,,r_{in}>0,r_{out}>0$.
Output: $\mathcal{G}_{1},\mathcal{G}_{2},\ldots\mathcal{G}_{c}$. Each
$\mathcal{G}_{i}$ is a collection of _buckets_ (_i.e.,_ sets of points of
$P$). Each bucket $G\in\mathcal{G}_{i}$ is labeled with _a bit-string_ , which
is a concatenation of sub-bit-strings $\textsc{lab}_{in}(G,1)$,
$\textsc{lab}_{out}(G,1)$, $\textsc{lab}_{in}(G,2)$,
$\textsc{lab}_{out}(G,2)$, $\ldots$, $\textsc{lab}_{in}(G,b)$,
$\textsc{lab}_{out}(G,b)$. For every $p\in P$ and $i=1,2,\ldots,c$, $p$
appears in one of the buckets in $\mathcal{G}_{i}$.

1: Initialize $\mathcal{G}_{i},i=1,2,\ldots,c$, as empty sets. Each
$\mathcal{G}_{i}$ will be used as a container for buckets.

2: Randomly sample $abc$ functions from family $\mathcal{H}_{in}$, and also
$abc$ functions from family $\mathcal{H}_{out}$. Denote these functions as
$h_{in,i,j,k}$ and $h_{out,i,j,k}$, for integers $1\leq i\leq a,1\leq j\leq
b,1\leq k\leq c$. For every $h_{in,i,j,k}$, $h_{out,i,j,k}$ and every $p\in
Q$, compute $F_{Z}(h_{in,i,j,k}(p))$ and $F_{Z}(h_{out,i,j,k}(p))$.

3: FOR $k$ from 1 to $c$:

  * •

For every point $p\in P$, we create a bit-string $S(p)$ that concatenates
$\textsc{lab}_{in}(p,1),\textsc{lab}_{out}(p,1),\textsc{lab}_{in}(p,2),\textsc{lab}_{out}(p,2),\ldots,\textsc{lab}_{in}(p,b),\textsc{lab}_{out}(p,b)$:
For $j$ from $1$ to $b$, let $\textsc{lab}_{in}(p,j)$,
$\textsc{lab}_{out}(p,j)$ be a pair of bit-strings of length $a$, each with
the $i$-th bit being $F_{Z}(h_{in,i,j,k}(p))$, $F_{Z}(h_{out,i,j,k}(p))$,
respectively, for $i=1,2,\ldots a$.

  * •

IF there is already a bucket $G$ in $\mathcal{G}_{k}$ with label $S(G)=S(p)$,
DO: Put $p$ into $G$.

  * •

ELSE, DO: Create a new bucket $G$ and put $G$ into $\mathcal{G}_{k}$, set the
label of $G$ as $S(G)=S(p)$. Put $p$ into $G$.

With the BD range query data structure created by the Algorithm 3, we can use
the Algorithm 4 below to answer a BD range query for any given pair of balls
$(B_{in}$ and $B_{out})$. The main idea of the algorithm compute a bit-string
label $S$ for the query, then examine points in buckets with labels that
satisfy certain properties (_e.g._ should have enough common bits with $S$).
Due to the fact that we label these buckets using functions from two LSH
families, it can be shown that the chance for us to find a point in
$B_{in}(1+\xi)\setminus B_{out}((1+\xi)^{-1})$ from one of the examined
buckets will be high if there exists a point in $B_{in}\setminus B_{out}$.

Algorithm 4 BD-Query$(B_{in},B_{out})$

Input: Two $\mathbb{R}^{d}$ balls: $B_{in}$ with center $o_{in}$ and radius
$r_{in}$, and $B_{out}$ with center $o_{out}$ and radius $r_{out}$. Assume
that collections $\mathcal{G}_{1},\mathcal{G}_{2},\ldots\mathcal{G}_{c}$ have
already been generated by algorithm CreateBucket.
Output: A point $p\in Q$, or NULL.
Note: The algorithm probes a number of points in the buckets of
$\mathcal{G}_{1},\mathcal{G}_{2},\ldots\mathcal{G}_{c}$ until a suitable point
is found as the output, or terminates and returns NULL when no such point can
be found or the number of probes exceeds a certain limit.

1: Do the following, but terminate and return NULL when $3c$ points are
examined: FOR $k$ from $1$ to $c$:

  * •

Create a bit string $S$ that concatenates $\textsc{lab}_{in}(o_{in},1)$,
$\textsc{lab}_{out}(o_{out},1)$, $\textsc{lab}_{in}(o_{in},2)$,
$\textsc{lab}_{out}(o_{out},2)$, $\ldots$, $\textsc{lab}_{in}(o_{in},b)$,
$\textsc{lab}_{out}(o_{out},b)$: For $j$ from $1$ to $b$, let
$\textsc{lab}_{in}(o_{in},j)$, $\textsc{lab}_{out}(o_{out},j)$ be a pair of
bit strings of length $a$, with the $i$-th bit of each string being
$F_{Z}(h_{in,i,j,k}(o_{in}))$, $1-F_{Z}(h_{out,i,j,k}(o_{out}))$,
respectively, for $i=1,2,\ldots a$.

  * •

Create a bit string $S^{\prime}$ that concatenates
$\textsc{lab}_{in}^{\prime}(1),\textsc{lab}_{out}^{\prime}(1),\textsc{lab}_{in}^{\prime}(2),\textsc{lab}_{out}^{\prime}(2),\ldots,$
$\textsc{lab}_{in}^{\prime}(b),\textsc{lab}_{out}^{\prime}(b)$: Each of these
sub bit strings is a random bit string of length $a$, drawn uniformly randomly
from $\\{0,1\\}^{a}$.

  * •

If there exists some integer $j$ such that
$\text{COM}(\textsc{lab}_{in}(o_{in},j),\textsc{lab}_{in}^{\prime}(j))<t_{1}$
or
$\text{COM}(\textsc{lab}_{out}(o_{out},j),\textsc{lab}_{out}^{\prime}(j))<t_{2}$,
where $\text{COM}(x,y)$ counts the number of common digits of 2 bit strings
$x,y$, $t_{1}=\mathsf{P}^{\prime}_{1}a-\eta a,t_{2}=(1-\mathsf{P}_{2})a/2-\eta
a$ CONTINUE.

  * •

If there is no bucket in $\mathcal{G}_{k}$ that is labeled with $S^{\prime}$,
CONTINUE.

  * •

Examine all the points in the bucket $G$ in $\mathcal{G}_{k}$ that is labeled
with $S^{\prime}$. Stop when there a point $p\in G$ such that $p\in
B_{in}(1+\xi)\setminus B_{out}((1+\xi)^{-1})$. Return $p$.

2:Return NULL if no point is returned in the above process.

In the following we show the correctness of Algorithm 4. Consider the for loop
in Step 1 of Algorithm 4 when answering a query $(B_{in},B_{out})$. Using the
notations from Algorithm 4, for any $k$ from 1 to $c$ in Step 1, we have the
following lemma, which shows that if a point in $P$ lies in (or outside of)
the query range, the number of common bits between its bucket label and the
label computed from the query would likely (or unlikely) be high,
respectively.

######  Lemma 2.5.

Let $p\in P$ be a point that lies in $B_{in}\setminus B_{out}$, and $q\in P$
be a point that does NOT lie in $B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1})$. Let
$S(p)=\textsc{lab}_{in}(p,1),\textsc{lab}_{out}(p,1),\textsc{lab}_{in}(p,2),\textsc{lab}_{out}(p,2)$,
$\ldots,\textsc{lab}_{in}(p,b),\textsc{lab}_{out}(p,b)$ and
$S(q)=\textsc{lab}_{in}(q,1),\textsc{lab}_{out}(q,1),\textsc{lab}_{in}(q,2),\textsc{lab}_{out}(q,2),\ldots$,
$\textsc{lab}_{in}(q,b),\textsc{lab}_{out}(q,b)$ be the labels of the bucket
in $\mathcal{G}_{k}$ that contains $p$ and $q$, respectively. For any
$j=1,2,\ldots,b$, the following holds.

  * •

$\text{Pr}[\text{COM}(\textsc{lab}_{in}(p,j),\textsc{lab}_{in}(o_{in},j))\geq
t_{1}\wedge\text{COM}(\textsc{lab}_{out}(p,j),\textsc{lab}_{out}(o_{out},j))\geq
t_{2}]\geq 4/9$.

  * •

$\text{Pr}[\text{COM}(\textsc{lab}_{in}(q,j),\textsc{lab}_{in}(o_{in},j))\geq
t_{1}\wedge\text{COM}(\textsc{lab}_{out}(q,j),\textsc{lab}_{out}(o_{out},j))\geq
t_{2}]\leq 1/3$.

######  Proof 2.6.

Since $p\in B_{in}\setminus B_{out}$, we have $\lVert p-o_{in}\rVert\leq
r_{in}$ and $\lVert p-o_{out}\rVert\geq r_{out}$. For any hash function
$h_{1}\in\mathcal{H}_{in}$ and $h_{2}\in\mathcal{H}_{out}$,
$\text{Pr}[h_{1}(p)=h_{1}(o_{in})]\geq\mathsf{P}_{1}$ and
$\text{Pr}[h_{2}(p)=h_{2}(o_{out})]\leq\mathsf{P}_{2}$. Thus, we have
$\text{Pr}[F_{Z}(h_{1}(p))=F_{Z}(h_{1}(o_{in}))]\geq(\mathsf{P}_{1}+1)/2$ and
$\text{Pr}[F_{Z}(h_{2}(p))=1-F_{Z}(h_{2}(o_{out}))]\leq(1-\mathsf{P}_{2})/2$.
This means that for any $i=1,2\ldots,a$, the probability that the $i$-th bit
of $\textsc{lab}_{in}(p,j)$ is the same as that of
$\textsc{lab}_{in}(o_{in},j)$ is at least
$\mathsf{P}^{\prime}_{1}=(\mathsf{P}_{1}+1)/2$. Since the hash functions to
determine each of the bits are drawn independently, an estimation of
$X=\text{COM}(\textsc{lab}_{in}(p,j),\textsc{lab}_{in}(o_{in},j))$ can be
obtained by
$\text{Pr}[F_{Z}(h_{1}(p))=F_{Z}(h_{1}(o_{in}))]\geq(\mathsf{P}_{1}+1)/2$
using the concentration inequalities for binomial distributions. Using a
variant of the Chernoff inequalities from [30], we have

$\text{Pr}[X\leq\mathsf{P}^{\prime}_{1}a-\eta a]\leq e^{-(\eta
a)^{2}/(2\mathsf{P}^{\prime}_{1}a)}.$

From the definition of the parameters, we know that
$\text{Pr}[X\leq\mathsf{P}^{\prime}_{1}a-\eta a]\leq 1/3$ (by simple
calculation). Thus, we have $\text{Pr}[X\geq t_{1}]\geq 2/3$.

Let $Y=\text{COM}(\textsc{lab}_{out}(p,j),\textsc{lab}_{out}(o_{out},j))$.
From
$\text{Pr}[F_{Z}(h_{2}(p))=1-F_{Z}(h_{2}(o_{out}))]\leq(1-\mathsf{P}_{2})/2$
and using a similar argument as above, we can also obtain $\text{Pr}[Y\geq
t_{2}]\geq 2/3$ (the details are omitted). Since the hash functions are drawn
independently, we have $\text{Pr}[X\geq t_{1}\wedge Y\geq t_{2}]\geq 4/9$.

In the following we discuss the case that $q\not\in B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1})$. This means either $\lVert
q-o_{in}\rVert\geq(1+\xi)r_{in}$ or $\lVert
q-o_{out}\rVert\leq(1+\xi)^{-1}r_{out}$. We first consider the case $\lVert
q-o_{in}\rVert\geq(1+\xi)r_{in}$. For any hash function
$h_{1}\in\mathcal{H}_{in}$,
$\text{Pr}[h_{1}(q)=h_{1}(o_{in})]\leq\mathsf{P}_{2}$. Thus, we have
$\text{Pr}[F_{Z}(h_{1}(q))=F_{Z}(h_{1}(o_{in}))]\leq(\mathsf{P}_{2}+1)/2$.
This means that for any $i=1,2\ldots,a$, the probability that the $i$-th bit
of $\textsc{lab}_{in}(q,j)$ is the same as that of
$\textsc{lab}_{in}(o_{in},j)$ is at most
$\mathsf{P}^{\prime}_{2}=(\mathsf{P}_{2}+1)/2$. Again, we use a concentration
inequality to obtain an estimation of
$X=\text{COM}(\textsc{lab}_{in}(q,j),\textsc{lab}_{in}(o_{in},j))$. Using a
variant of the Chernoff inequalities from [30], we have

$\text{Pr}[X\geq\mathsf{P}^{\prime}_{2}a+\eta a]\leq e^{-(\eta
a)^{2}/(2\mathsf{P}^{\prime}_{2}a+\eta a/3)}.$

Note that $a=(2\mathsf{P}^{\prime}_{1}\ln
3)/\eta^{2}\geq((2\mathsf{P}^{\prime}_{2}+\eta/3)\ln 3)/\eta^{2}$, which
implies that $e^{-(\eta a)^{2}/(2\mathsf{P}^{\prime}_{2}a+\eta a/3)}\leq 1/3$
(by simple calculation). Thus, we have
$\text{Pr}[X\geq\mathsf{P}^{\prime}_{2}a+\eta a]\leq 1/3$. Also, since
$\mathsf{P}^{\prime}_{2}a+\eta a<\mathsf{P}^{\prime}_{1}a-\eta a=t_{1}$, we
get $\text{Pr}[X\geq t_{1}]\leq 1/3$. This immediately implies that
$\text{Pr}[\text{COM}(\textsc{lab}_{in}(q,j),\textsc{lab}_{in}(o_{in},j))\geq
t_{1}\wedge\text{COM}(\textsc{lab}_{out}(q,j),\textsc{lab}_{out}(o_{out},j))\geq
t_{2}]\leq 1/3$.

The argument for the case $\lVert q-o_{out}\rVert\leq(1+\xi)^{-1}r_{out}$ is
similar. Thus, we omit it here. This completes the proof.

From the above lemma, we can conclude the following by basic calculation. For
any $k$ from 1 to $c$ in Step 1 of Algorithm 4 (if the loop is actually
executed), let $p\in P$ be a point that lies in $B_{in}\setminus B_{out}$, and
$q\in P$ be a point that does NOT lie in $B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1})$, we have the following.

######  Lemma 2.7.

Let $G_{p}$ and $G_{q}$ be the buckets in $\mathcal{G}_{k}$ that contain $p$
and $q$, respectively. The probability for $G_{p}$ to be examined is no
smaller than $2^{-2ab}(4/9)^{b}=(\mathsf{P}^{\prime\prime}_{1})^{b}$, and the
probability for the event “ALL such $G_{p}$ for $k$ from 1 to $c$ are NOT
examined” is at most $(1-(\mathsf{P}^{\prime\prime}_{1})^{b})^{c}\leq 1/e$.
The probability for $G_{q}$ to be examined is no larger than
$2^{-2ab}(1/3)^{b}=(\mathsf{P}^{\prime\prime}_{2})^{b}\leq 1/n$.

With the above lemma, we can obtain the following lemma using an argument
similar to [28] for near neighbor search with LSH. This proves the correctness
of the query scheme.

######  Lemma 2.8.

If there exists a point in $P$ that lies in $B_{in}\setminus B_{out}$, with
probability at least $1/4$, Algorithm 4 reports a point in $P$ that lies in
$B_{in}(1+\xi)\setminus B_{out}((1+\xi)^{-1})$.

The complexity of the data structure is $O(dabcn)$, which is
$O_{\xi}(dn^{1+\rho}\log n)$ from $a=O_{\xi}(1),b=O_{\xi}(\log n)$ and
$c=O_{\xi}(n^{\rho})$, and $\rho$ and the constant hidden in the big-O
notation depends only on $\xi$. The query time is $O(abcd)$, which is
$O_{\xi}(dn^{\rho}\log n)$. To achieve $1-\delta$ success probability, it
suffices to concatenate $O(\log\delta)$ such data structures together.

We leave the proof of the above 2 lemmas and the full proof of Lemma 2.2 to
the appendix for readability.

##  3 Multi-scale Construction

In this section, we present the multi-scale construction method, which is a
standalone technique with potential to be used to other high dimensional
range-aggregate query problems.

The multi-scale construction method is motivated by several high dimensional
geometric query problems that share the following common feature: they are
challenging in the general settings, but become more approachable if some key
parameters are known in advance. The AIFP query problem discussed in this
paper is such an example. In the previous section, we have shown how to
construct an AIFP data structure if we fix the size of the query ball and know
that the farthest distance lies in a given range.

The basic ideas behind multi-scale construction are the follows. Firstly, we
know that if a problem is solvable when one or more key parameters are fixed,
a feasible way to solve the general case of the problem is to first enumerate
all possible cases of the problem defined by (the combinations of) the values
of the parameters. Then, solve each case of the problem, and finally obtain
the solution from that of all the enumerated cases. The multi-scale
construction method follows a similar idea. More specifically, to obtain a
general AIFP query data structure, the multi-scale construction method builds
a set of constrained AIFP query data structures that cover all possible radii
of $B$ and farthest distance value. Secondly, since it is impossible to
enumerate the infinite number of all possible values for these parameters, our
idea is to sample a small set of fixed radii (based on the distribution of the
points in $P$) and build constrained AIFP data structures only for the set of
sampled values. This will certainly introduce errors. However, good
approximations are achievable by using a range cover technique.

Below we first briefly introduce two key ingredients of our method,
Aggregation Tree and Range Cover, and then show how they can be used to form a
multi-scale construction.

###  3.1 Aggregation Tree and Range Cover

In this subsection, we briefly introduce the two components of the multi-scale
construction scheme: the _aggregation tree_ and the _range cover_ data
structure. We first introduce aggregation tree, which is used in [31] as an
ingredient of the range cover data structure. It is essentially a slight
modification of the Hierarchical Well-Separated Tree (HST) introduced in [32].
Below is the definition of an aggregation tree: (1) Every node $v$ (called
aggregation node) represents a subset $P(v)$ of $P$, and the root represents
$P$; (2)Every aggregation node $v$ is associated with a representative point
$re(v)\in P(v)$ and a size $s(v)$. Let $Dia(P(v))$ denotes the diameter of
$P(v)$, $s(v)$ is a polynomial approximation of $Dia(P(v))$: $Dia(P(v))\leq
s(v)$, and $\frac{s(v)}{Dia(P)}$ is upper-bounded by a polynomial function
$\mathcal{P}_{HST}(n,d)\geq 1$ (called distortion polynomial); (3) Every leaf
node corresponds to one point in $P$ with size $s(v)=0$, and each point
appears in exactly one leaf node; (4) The two children $v_{1}$ and $v_{2}$ of
any internal node $v$ form a partition of $v$ with $\max\\{s(v_{1}),$
$s(v_{2})\\}<s(v)$; and (5) For every aggregation node $v$ with parent
$v_{p}$, $\frac{s(v_{p})}{r_{out}}$ is bounded by the distortion polynomial
$\mathcal{P}_{HST}(n,d)\geq 1$, where $r_{out}$ is the minimum distance
between points in $P(v)$ and points in $P\setminus P(v)$.

The above definition is equivalent to the properties of HST in [32], except
that we have an additional distortion requirement (Item 5). See Figure 2 for
example of an aggregate tree.

Figure 2: An illustration of an aggregation tree built for 6 points.

An aggregation tree can be constructed in $O(dn\log^{2}n)$ time using the
method in [32]. It is proved in [32] that the distortion polynomial is
$\mathcal{P}_{HST}(n,d)=dn$. In the rest of the paper, we always assume that
the distortion of an aggregation tree is $\mathcal{P}_{HST}(n,d)=dn$.

Algorithm 5 RangeCover$(T_{P};\lambda,\Delta)$

Input: An aggregation tree $T_{P}$ built over a set $P$ of $n$ points in
$\mathbb{R}^{d}$; controlling factors $0<\lambda<1$ and an integer $\Delta\geq
4\mathcal{P}_{HST}(n,d)$.
Output: A number of buckets, where each bucket stores a number of tree nodes.
Each bucket $B_{t}$ is indexed by an integer $t$ and associated with an
interval $((1+\lambda)^{t},(1+\lambda)^{t+1}]$.

1: For every integer $t$ create an empty bucket $B_{t}$ associated with
interval $((1+\lambda)^{t},(1+\lambda)^{t+1}]$. (Note that $B_{t}$ will not be
actually created until some tree node $v$ is inserted into it.)

2: For every non-root node $v$ of $T_{P}$, let $v_{p}$ be its parent in
$T_{P}$, $r_{H}$ be $s(v_{p})/\lambda$, and $r_{L}$ be
$\max\\{s(v)/\lambda,s(v_{p})/\Delta\\}$. Do

  * •

For every integer $t$ satisfying inequality $r_{L}\leq(1+\lambda)^{t}<r_{H}$,
insert $v$ into bucket $B_{t}$.

In the following, we briefly introduce range cover. Range cover is a technique
proposed in [31] for solving the truth discovery problem in high dimensions.
We utilize it in a completely different way to form a multi-scale construction
for the AIFP query problem. Below is the algorithm (Algorithm 5). Given an
aggregation tree $T_{p}$ and real number parameters $\Delta\geq 8n$ and
$0<\lambda<1$ (whose values will be determined later), the range cover
algorithm creates a number of buckets for the nodes of $T_{P}$. Each bucket
$B_{t}$ is associated with an interval of real number
$((1+\lambda)^{t},(1+\lambda)^{t+1}]$. If a value $r$ lies in the interval of
a bucket $B_{t}$, it can be shown that the diameter of every aggregation node
$v$ is small compared to $r$, and thus all points in $P(v)$ can be
approximately viewed as one “heavy” point located at the representative point
$re(v)$. Intuitively, every bucket from the range cover algorithm provides a
view of $P$ when observed from a distance $r$ in the range of the bucket,
where each node in the bucket represents a “heavy” point that is formed by the
aggregation of a set of close (compared to the observing distance) clusters of
points in $P$. Thus, the buckets of the range cover provides views of the
input point set at different scales of observing distances (see Figure 3 for
an illustration). The size of the output data structure is only $O(n\log
n\Delta)$, as shown in [31].

Figure 3: An illustration of range cover. The nodes in every bucket can be
viewed as “heavy” points yielded by the aggregation of a set of close points.
Every bucket provides a view of the input point set when observed from a
certain distance. All the buckets jointly form a complete set of views of the
input points at all possible scales.

Note that for many problems, fixing some key parameters also means fixing the
“observing distance” of $P$ from the perspective of solving the problem. This
allows us to solve the problem based on the view of $P$ provided by the bucket
associated with the corresponding observation distance. We will show that this
idea also applies to the AIFP problem.

###  3.2 Multi-scale Construction for AIFP

In this subsection, we use AIFP problem as an example to show how to implement
multi-scale construction using the range cover data structure.

We first observe that every bucket of the range cover can be used to solve a
constrained AIFP problem (with the proof given later). Given an AIFP query
$(B,q)$, if the (approximate) distance from $q$ to a point in $P\cap B$ is
known and falls in the interval of $((1+\lambda)^{t},(1+\lambda)^{t+1}]$, then
the (approximate) distance from $q$ to a point of $B_{t}\cap B$ (where every
node $v$ in $B_{t}$ is viewed as a “heavy” point located at $re(v)$) is an
AIFP of $q$ in $P\cap B$. This means that $B_{t}$ provides a good “sketch” of
$P$ that allows more efficient computation of the AIFP of $q$ in $P\cap B$.
This observation leads to the main idea of the multi-scale construction
method. To obtain a general AIFP query data structure, for every bucket
$B_{t}$, we construct a constrained AIFP data structure for $B_{t}$ (viewed as
a set of “heavy” points), exploiting the assumption that the farthest distance
is in the interval of $((1+\lambda)^{t},(1+\lambda)^{t+1}]$. To answer a
general AIFP query, we can find the AIFP for every bucket by querying the
constrained AIFP data structures associated with the bucket. In this way, we
can compute AIFPs for all possible radii. When answering a general AIFP query,
we first determine an approximate farthest distance of $q$ to $P\cap B$, and
then query the appropriate constrained AIFP data structures. Despite the
necessity of building multiple constrained data structures, the complexity of
the multi-scale construction is not high, as the total number of nodes in all
buckets is only $\tilde{O}(n)$.

However, the above idea is hard to implement, because each bucket $B_{t}$ is
only responsible for a small range $((1+\lambda)^{t},(1+\lambda)^{t+1}]$ of
the possible farthest distance from $q$ to $P\cap P$. This means that we need
an accurate estimation of this distance when answering the query, which is
almost as hard as the query itself. We resolve this issue by merging multiple
consecutive buckets into a larger one. The resulting bucket can account for a
larger range of the possible farthest distances. We then build a constrained
data structure for each bucket.

This leads to the following Multi-Scale algorithm. Let $\Gamma\geq 1$ be an
integer constant to be determined, and $\mathcal{A}$ be an algorithm for
building a constrained data structure. In this algorithm, for each integer
$t$, we try to merge the aggregation nodes in buckets
$B_{t},B_{t+1},\ldots,B_{t+\Gamma}$ from the range cover (recall that these
buckets are associated with farthest distance ranges
$((1+\lambda)^{t},(1+\lambda)^{t+1}],((1+\lambda)^{t+1},(1+\lambda)^{t+2}]\ldots,((1+\lambda)^{t+\Gamma},(1+\lambda)^{t+\Gamma+1}]$,
respectively) into one bucket $B^{+}_{t}$ that could account for a larger
range $((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$. We then use $\mathcal{A}$
to build a data structure $\mathcal{S}_{t}$ for every bucket $B^{+}_{t}$ (by
viewing every node in $B^{+}_{t}$ as a point).

Algorithm 6 Multi-Scale$(T_{P};\lambda,\Delta,\Gamma;\mathcal{A})$

Input: An aggregation tree $T_{P}$ built over a set $P$ of $n$ points in
$\mathbb{R}^{d}$; controlling factors $0<\lambda<1$, integer $\Delta\geq
4\mathcal{P}_{HST}(n,d)=4dn$, and integer $\Gamma\geq 1$. A routine
$\mathcal{A}$ which builds a constrained data structure for any given bucket
$B_{t}$ and point set $re(B^{+}_{t}):=\\{re(v)\mid v\in B^{+}_{t}\\}$.
Output: A number of buckets, with each storing a number of tree nodes. Each
bucket $B^{+}_{t}$ is indexed by an integer $t$ and associated with an
interval $((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$. Each bucket $B^{+}_{t}$
is associated with data structure $\mathcal{S}_{t}$ built by $\mathcal{A}$.

1: Create a collection of buckets $\\{B_{t}\\}$ by calling
RangeCover($T_{P};\lambda,\Delta(1+\lambda)^{\Gamma}$).

2: For each integer $t$ create an empty bucket $B^{+}_{t}$ associated with
$((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$.

3: For every non-root node $v$ of $T_{P}$, enumerated in a bottom-up manner in
$T_{P}$ so that the children of a node is always visited earlier than the
parent node, put $v$ into $B^{+}_{t}$ for every $t$ such that the following is
satisfied:

  * •

$s(v)\leq\lambda(1+\lambda)^{t}$, $v$ appears in
$B_{t^{\prime}}\in\\{B_{t}\\}$ for some $t\leq t^{\prime}\leq t+\Gamma$, and
none of $v$’s descendants are put in $B^{+}_{t}$ previously.

4: For every non-empty bucket $B^{+}_{t}$, create a data structure
$\mathcal{S}_{t}$ using $\mathcal{A}$ for the point set
$re(B^{+}_{t}):=\\{re(v)\mid v\in B^{+}_{t}\\}$.

For better understanding of this scheme, we first briefly discuss the
geometric properties of the buckets created by Algorithm 6. Intuitively
speaking, the aggregation nodes of every bucket provide a sketch of _almost_
the whole input point set $P$, with the exception being points that satisfying
some special isolation property. This can be briefly described as follows: (1)
The diameter of each the aggregation node (viewed as a point set) should be
small to the observation distances; (2) The aggregation nodes are mutually
disjoint; and (3) Every point $p\in P$ is either in one of the nodes in the
bucket, or it is in an aggregation node (not in the bucket) whose distance to
other nodes is large. These properties are formalized as follows. (We leave
the proofs of all the following claims and lemma to the full version of the
paper.)

######  Claim 1.

Let $v$ be any aggregation node $v$ in a created bucket $B^{+}_{t}$. Then,
$s(v)\leq\lambda(1+\lambda)^{t}$.

######  Lemma 3.1.

For any $p\in P$ and and bucket $B^{+}_{t}$ created by Algorithm 6, one of the
following holds:

  1. 1.

There exists exactly one aggregation node $v\in B^{+}_{t}$ such that $p\in
P(v)$.

  2. 2.

Either $B^{+}_{t}$ is empty or there exists no aggregation node $v\in
B^{+}_{t}$ such that $p\in P(v)$. There exists an aggregation node
$v^{\prime}$ in $T_{P}$ such that $s(v^{\prime})/\lambda\leq(1+\lambda)^{t}$.
Furthermore, let $q$ be any point in $P\setminus P(v^{\prime})$, then $\lVert
p-q\rVert>(\Delta/dn)(1+\lambda)^{t+\Gamma}$.

######  Proof 3.2.

Note that for any two nodes of the aggregation tree $T_{P}$, either the
associated point sets of the two nodes are disjoint, or one of the node is a
descendant of the other. Since in Algorithm 6, we avoid putting a node in
$B^{+}_{t}$ when the node’s descendant is already in $B^{+}_{t}$. Thus the
associated sets of the nodes in $B^{+}_{t}$ are disjoint. Clearly there exists
no more than one $v\in B^{+}_{t}$ such that $p\in P(v)$.

In the following, we let $v_{0}$ be the leaf of $T_{P}$ such that
$P(v_{0})=\\{p\\}$. Let $v^{\prime}$ be the farthest ancestor of $v_{0}$ in
$T_{P}$ such that $s(v^{\prime})/\lambda\leq(1+\lambda)^{t}$. We show that
either $v^{\prime}\in B^{+}_{t}$, or $\lVert
p-q\rVert>(\Delta/dn)(1+\lambda)^{t+\Gamma}$ for any point $q$ in $P\setminus
P(v^{\prime})$. We assume that $v^{\prime}$ is not the root of $T_{P}$, since
otherwise we are done. Let $v^{\prime\prime}$ be the parent of $v^{\prime}$ in
$T_{P}$. Let $\Delta^{\prime}:=\Delta\cdot(1+\lambda)^{\Gamma}$ (_i.e._ ,
$\Delta^{\prime}$ is the third parameter passed to the call to RangeCover in
Step 1 of Algorithm 6). Clearly,
$s(v^{\prime})/\lambda\leq(1+\lambda)^{t}<s(v^{\prime\prime})/\lambda$. We
consider three cases: (1) $s(v^{\prime\prime})/\lambda>(1+\lambda)^{t}\geq
s(v^{\prime})/\lambda\geq s(v^{\prime\prime})/\Delta^{\prime}$; (2)
$s(v^{\prime\prime})/\lambda>(1+\lambda)^{t}\geq
s(v^{\prime\prime})/\Delta^{\prime}>s(v^{\prime})/\lambda$; and (3)
$s(v^{\prime\prime})/\lambda>s(v^{\prime\prime})/\Delta^{\prime}>(1+\lambda)^{t}\geq
s(v^{\prime})/\lambda$.

Case (1) and (2). Clearly, in this case, $v^{\prime}\in B_{t}$. Note that
since $s(v^{\prime})\lambda\leq(1+\lambda)^{t}$, we know that any proper
descendant of $v^{\prime}$ will not be put in a bucket $B_{t^{\prime}}$ for
any $t^{\prime}\geq t$. Thus, we have $v^{\prime}\in B^{+}_{t}$.

Case (3). Assume that $v^{\prime}\not\in B^{+}_{t}$. From the property of the
aggregation tree, we know that for any $q\in P\setminus P(v^{\prime})$,
$\lVert q-p\rVert\geq
s(v^{\prime\prime})/nd>(\Delta^{\prime}/nd)(1+\lambda)^{t}=(\Delta/nd)(1+\lambda)^{t+\Gamma}$.
This completes the proof.

Although the sketch does not fully cover $P$, in many problems (including
AIFP) these points are either negligible or easy to handle by other means due
to their special properties.

From [31], we know that the running time of Algorithm 5 and the space
complexity of the output data structure is $O_{\lambda}(n\log n\Delta)$ (where
the hidden constant in the big-O notation depends only on $\lambda$).
Algorithm 6 essentially merges $\Gamma+1$ consecutive buckets $B_{t}$,
$B_{t+1}$, $\ldots$, $B_{t+\Gamma}$ created by Algorithm 5 into one bucket
$B^{+}_{t}$. Thus, we have the following lemma.

######  Lemma 3.3.

Excluding the time it takes for $\mathcal{A}$ to process each $B^{+}_{t}$ in
Step 4, the running time of Algorithm 6 and the total number of nodes in all
buckets is $O_{\lambda}(\Gamma^{2}n\log n\Delta)$, where the hidden constant
in big-O notation depends only on $\lambda$.

We conclude this subsection by providing a key lemma showing that, given a
constrained AIPF query $(B,q)$ satisfying constraint $(r_{B},d_{min},d_{max})$
with $d_{min}\leq r_{B}\leq d_{max}$, if there is a bucket $B^{+}_{t}$ such
that
$(1+\lambda)^{t+1}/(1-\lambda)<d_{min}<d_{max}\leq(1+\lambda)^{t+\Gamma}-(2+2/\lambda)r_{B}$
(_i.e._ the range $[d_{min},d_{max}]$ falls in interval
$((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$ with some gap), then, with an
easy-to-handle exception, an AIFP to $q$ in $B^{+}_{t}$ (by viewing every node
of $B^{+}_{t}$ as one point) in (slightly enlarged) range $B$ is also an AIFP
of $q$ to $P\cap B$. Formally, let $re(B^{+}_{t}):=\\{re(v)\mid v\in
B^{+}_{t}\\}$. Let $p_{t}$ be the farthest point to $q$ in $re(B^{+}_{t})\cap
B(1+\lambda)$ if $re(B^{+}_{t})\cap B(1+\lambda)\not=\emptyset$, and $p$ be a
$(\lambda/6,\lambda/6)$-AIFP of $q$ in $re(B^{+}_{t})\cap B(1+\lambda)$
222Note $p$ could be NULL here. This could happen when bucket $B^{+}_{t}$ is
empty or $re(B^{+}_{t})\cap B(1+\lambda)=\emptyset$. . Let $p_{N}$ be a
$(1+\lambda)$-approximate nearest neighbor of $q$ in $P$.

######  Lemma 3.4.

One of the following holds: (1) $p_{N}$ is a $(2\lambda,2\lambda)$-AIFP of q
in $P\cap B$, or (2) $p_{t}$ exists and $(1+\lambda)^{t}\leq\lVert
q-p_{t}\rVert\leq(1+\lambda)^{t+\Gamma+1}$, and $p$ is a
$(2\lambda,2\lambda)$-AIFP of $q$ in $P\cap B$.

######  Proof 3.5.

We first consider the case where there exists a point $p\in P\cap B$, such
that there does NOT exist $v(p)\in B^{+}_{t}$ with $p\in P(v(p))$. We will
show that in this case, item (1) of the lemma holds.

If such a $p$ exists, by Lemma 3.1, we know that there exists an aggregation
node $v^{\prime}$ such that $p\in P(v^{\prime})$,
$s(v^{\prime})\leq\lambda(1+\lambda)^{t}<\lambda d_{min}$, and for any
$p^{\prime}\in P\setminus P(v^{\prime})$, $\lVert
p-p^{\prime}\rVert>(\Delta/dn)(1+\lambda)^{t+\Gamma}\geq
4(d_{max}+(2+2\lambda)r_{B})\geq 4(\lVert p-q\rVert+(2+2\lambda)r_{B})$. Since
$p$ lies in $B$, it is not hard to see that $p^{\prime}$ does not lie in
$B(1+\lambda)$. This implies if a point lies in $P\cap B$, then it is in
$P(v^{\prime})$. Let $p_{f}$ be the farthest point to $q$ in $B\cap P$. Thus
$p_{f}\in P(v^{\prime})$. For any point $p^{\prime\prime}\in P(v^{\prime})$,
we have $\lVert p^{\prime\prime}-p_{f}\rVert\leq s(v^{\prime})\leq\lambda
d_{min}\leq\lambda\lVert q-p_{f}\rVert$, therefore $\lVert
q-p^{\prime\prime}\rVert\geq\lVert q-p_{f}\rVert-\lVert
p^{\prime\prime}-p_{f}\rVert\geq(1-\lambda)\lVert q-p_{f}\rVert$. Also we have
$\lVert p^{\prime\prime}-p_{f}\rVert\leq\lambda d_{min}\leq\lambda r_{B}$.
Since $p_{f}\in B$, it is not hard to see $p^{\prime\prime}\in B(1+\lambda)$.
We have shown that any point $p^{\prime\prime}\in P(v^{\prime})$ is an
$(\lambda,\lambda)$-AIFP of $q$ in $B\cap P$. Next, we show that $P_{N}\in
p(v)$. Recall that for any $p^{\prime}\in P\setminus P(v^{\prime})$, $\lVert
p-p^{\prime}\rVert\geq 4(\lVert p-q\rVert+(2+2\lambda)r_{B})$. We have $\lVert
q-p^{\prime}\rVert\geq\lVert p-p^{\prime}\rVert-\lVert q-p\rVert\geq 3(\lVert
p-q\rVert+(2+2\lambda)r_{B})$. On the other hand, since $p_{f}\in B$, we have
$\lVert p_{f}-q\rVert\leq\lVert p_{f}-p\rVert+\lVert p-q\rVert\leq
2r_{B}+\lVert p-q\rVert$. Therefore, $\lVert p_{f}-q\rVert<\lVert
p-p^{\prime}\rVert/2$, thus $p^{\prime}$ cannot be a $(1+\lambda)$-approximate
nearest neighbor of $q$ in $P$. We have proved item (1) of the lemma in this
case.

In the following, we assume that for any $p\in P\cap B$, there exist $v(p)\in
B^{+}_{t}$ with $p\in P(v(p))$. We prove item (2) of the lemma holds in this
case.

Let $p_{f}$ be the farthest point to $q$ in $B\cap P$. (Note we can assume
that $p_{f}$ exists, otherwise $B\cap P=\emptyset$, which means any point in
$P$ is an AIFP of $q$, and item (1) of the lemma trivially holds.) We first
show $p_{t}$ exists and $\lVert q-p_{t}\rVert\geq(1+\lambda)^{t}$. Let
$v_{f}\in B^{+}_{t}$ be the node such that $p_{f}\in P(v_{f})$. We have
$\lVert p_{f}-re(v_{f})\rVert\leq
s(v_{f})\leq\lambda(1+\lambda)^{t}\leq\lambda r_{B}$. Since $p_{f}\in B$, we
have $re(v_{f})\in B(1+\lambda)$. This means $B(1+\lambda)\cap re(B^{+}_{t})$
is non-empty, thus $p_{t}$ exists. Also, since $re(v_{f})\in re(B^{+}_{t})$,
from the definition of $p_{t}$, we have $\lVert q-p_{t}\rVert\geq\lVert
q-re(v_{f})\rVert$. Thus $\lVert q-p_{t}\rVert\geq\lVert
q-re(v_{f})\rVert\geq\lVert q-p_{f}\rVert-\lVert p_{f}-re(v_{f})\rVert\geq
d_{min}-\lambda(1+\lambda)^{t}\geq d_{min}-\lambda
d_{min}\geq(1-\lambda)(1+\lambda)^{t+1}/(1-\lambda)\geq(1+\lambda)^{t}$.

Next we show $\lVert q-p_{t}\rVert\leq(1+\lambda)^{t+\Gamma+1}$. Clearly both
$p_{f}$ and $p_{t}$ are in $B(1+\lambda)$, thus $\lVert
p_{t}-p_{f}\rVert\leq(2+2\lambda)r_{B}$. We have $\lVert
q-p_{t}\rVert\leq\lVert q-p_{f}\rVert+\lVert p_{t}-p_{f}\rVert\leq
d_{max}+(2+2\lambda)r_{B}\leq(1+\lambda)^{t+\Gamma+1}$.

Finally, we prove that the point $p$, which is a $(\lambda/6,\lambda/6)$-AIFP
of $q$ in $P\cap B(1+\lambda)$, is a $(2\lambda,2\lambda)$-AIFP of $q$ in
$P\cap B$. Note $p\in B((1+\lambda)\cdot(1+\lambda/6))\subset B(1+2\lambda)$.
Also, note $\lVert p_{f}-re(v_{f})\rVert\leq
s(v_{f})\leq\lambda(1+\lambda)^{t}\leq\lambda d_{min}\leq\lambda\lVert
q-p_{f}\rVert$, Thus $\lVert q-re(v_{f})\rVert\geq\lVert q-p_{f}\rVert-\lVert
p_{f}-re(v_{f})\rVert\geq(1-\lambda)\lVert q-p_{f}\rVert$. For any $p_{B}\in
p\cap B$, We have $\lVert q-p\rVert\geq(1-\lambda/6)\lVert
q-re(v_{f})\rVert\geq(1-\lambda/6)(1-\lambda)\lVert
q-p_{f}\rVert\geq(1-\lambda/6)(1-\lambda)\lVert
q-p_{B}\rVert\geq(1-2\lambda)\lVert q-p_{B}\rVert$. We have proved $p$ is a
$(2\lambda,2\lambda)$-AIFP of $q$ in $P\cap B$.

The above lemma implies that, in Algorithm 6, if routine $\mathcal{A}$ builds
a constrained AIFP data structure for farthest distance lies in interval
$[(1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$, then either this data structure
can be used to answer any query with constraint $(r_{B},d_{min},d_{max})$
(with other parameters, like $r_{B}$ and the approximate factors for
constrained AIFP, set properly), or the AIFP query can be solved easily using
a nearest neighbor search. In the following section, we will show how to build
a general AIFP query data structure through multi-scale construction by
selecting appropriate parameters. With the multi-scale data structure
(together with some auxiliary data structures), we can answer an AIFP query by
(1) obtaining a rough estimation of the farthest distance, and (2) querying
the bucket corresponding to the estimated range.

##  4 General AIFP Query

In this section, we present a general $(\epsilon,\gamma)$-AIFP query scheme.
We first establish several facts for better understanding of the query scheme.
In the following, let $B$ be a closed ball with radius $r_{B}>0$ and $q$ be an
arbitrary point. Let $0<\epsilon<1$ and $0<\gamma<1$ be any pair of constants
and $\lambda:=\min(\epsilon,\gamma)/512$. We assume that $r_{B}$ is _$\lambda$
-aligned_, which means that $r_{B}=(1+\lambda)^{t}$ for some integer $t$. The
alignment assumption makes it easier to implement the multi-scale
construction. Note that if $r_{B}$ is not $\lambda$-aligned, we can always
enlarge $B$ a little to make $r_{B}$ aligned and still obtain a good
approximation with carefully chosen parameters.

Our main idea is to convert each query $(B,q)$ into one or more AIFP queries
$(B^{\prime},q)$ such that it is possible to find a lower bound
$d^{\prime}_{min}$ and an upper bound $d^{\prime}_{max}$ on the farthest
distance between $q$ and a point in $B^{\prime}\cap P$. With such bounds, the
AIFP can then be found by querying a pre-built constrained AIFP data
structure. To ensure efficiency, the gap between $d_{min}$ and $d_{max}$
cannot be too large, i.e., $d_{max}/d_{min}$ should be bounded by a polynomial
of $n$ and $d$. Since the complexity of a constrained data structure depends
on $d^{\prime}_{max}/d^{\prime}_{min}$, a small gap will also enable us to
control the size of the data structure. We start with a simple claim.

######  Claim 2.

If the distance between $q$ and the center $o_{B}$ of $B$ is very large
compared to $r_{B}$, _i.e._ $\lVert
q-o_{B}\rVert\geq(3+\gamma)\epsilon^{-1}r_{B}$, then any point in
$B(1+\gamma/2)$ is an $(\epsilon,\gamma)$-AIFP of $q$ in $P\cap B$.

This claim suggests that we can safely assume that the farthest distance
between $q$ and $P\cap B$ is not too large (compared to $r_{B}$), as otherwise
the AIFP can be easily found. This helps us establish an upper bound on the
farthest distance. In the following, we let
$d_{max}:=(4+2\gamma)\epsilon^{-1}r_{B}$, and assume that $\lVert
q-o_{B}\rVert\leq(3+\gamma)\epsilon^{-1}r_{B}$. From simple calculation, this
implies that for any $p\in P\cap B(1+\gamma)$, we have $\lVert p-q\rVert\leq
d_{max}$.

Next, we try to find a lower bound for the farthest distance. This process is
much more complicated. We need an aggregation tree $T_{P}$ with distortion
polynomial $\mathcal{P}_{HST}(n,d)=nd$. Later, we will use this $T_{P}$ to
construct the query data structure. Let $p_{N}\in P$ be a $2$-nearest neighbor
of $q$ in $P$ (_i.e._ for any $p^{\prime}\in P$, $\lVert p_{N}-q\rVert\leq
2\lVert p^{\prime}-q\rVert$), and $r_{N}$ be its distance to $q$ (i.e.,
$r_{N}:=\lVert p_{N}-q\rVert$). Denote by $v$ the lowest (closest to a leaf)
node of $T_{P}$ such that $p_{N}\in P(v)$ and $s(v)+r_{N}\leq\gamma r_{B}/64$.
Note that such a node may not exist (_i.e._ $r_{N}>\gamma r_{B}/64$), and we
will show that the AIFP can be found easily in such a case. We have the
following claims.

######  Claim 3.

If node $v$ does not exist, for any $p\in P$, $\lVert q-p\rVert\geq\gamma
r_{B}/256nd$; Otherwise, for any $p_{out}\in P\setminus P(v)$, $\lVert
q-p_{out}\rVert\geq\gamma r_{B}/256nd$.

The following two claims assume that $v$ does exist.

######  Claim 4.

If $\lVert o_{B}-q\rVert>(1+\gamma/64)r_{B}$, then for every $p\in P(v)$,
$p\not\in B$.

For any positive real number $x$, let $[x]_{\lambda}$ denote the smallest real
number that can be written as $(1+\lambda)^{t}$ for some integer $t$ such that
$(1+\lambda)^{t}\geq x$.

######  Claim 5.

Let $r^{-}:=r_{N}+s(v)$ and $r^{(2)}_{B}:=[(1+\gamma/16)r_{B}]_{\lambda}$. If
$\lVert o_{B}-q\rVert\leq(1+\gamma/64)r_{B}$, and $P\cap B\not=\emptyset$ then

  1. 1.

If $r^{-}>\gamma r_{B}/512n^{2}d^{2}$, there exists
$p_{1}\in\mathcal{B}(o_{B},r^{(2)}_{B})\cap P$ such that $\lVert
p_{1}-q\rVert\geq\gamma r_{B}/2048n^{3}d^{3}$.

  2. 2.

If $r^{-}\leq\gamma r_{B}/512n^{2}d^{2}$, the following holds, where
$r^{(3)}_{B}:=[r^{-}]_{\lambda}$. (a) $\mathcal{B}(q,r^{(3)}_{B})\subset
B(1+\gamma/32)$; (b) For every $p\in P(v)$, $p\in\mathcal{B}(q,r^{(3)}_{B})$
and for every $p\in P\setminus P(v)$,
$p\not\in\mathcal{B}(q,(1+\gamma)r^{(3)}_{B})$; (c) There exists
$p^{\prime}\in P(v)$ such that $\lVert p^{\prime}-q\rVert\geq
r^{(3)}_{B}/8nd$.

The above facts allow us to reduce the AIFP query to a constrained query with
an estimated lower bound on the farthest distance. We assume $P\cap
B\not=\emptyset$, otherwise the query becomes trivial. Let $p_{F}$ be the
farthest point to $q$ in $P\cap B$. Note that there are three possible cases:
$p_{F}\in P(v)$, $p_{F}\in P\setminus P(v)$, or $v$ does not exist. If
$p_{F}\in P\setminus P(v)$ or $v$ does not exist, from Claim 3 we know that
$(B,q)$ satisfies the constraint of
$(r^{(1)}_{B},d^{(1)}_{min},d^{(1)}_{max})$, where $r^{(1)}_{B}:=r_{B}$,
$d^{(1)}_{min}:=\gamma r_{B}/256nd$ and $d^{(1)}_{max}:=d_{max}$. Thus, these
two cases can be captured by performing a constrained AIFP query to the pre-
built data structures. Also note that
$d^{(1)}_{max}/d^{(1)}_{min}=256(4+2\gamma)nd/\epsilon$, which is a polynomial
of $n$ and $d$. This means that the space complexity of the pre-built data
structures can be bounded.

Next, we consider the case of $p_{F}\in P(v)$. Note that if $\lVert
o_{B}-q\rVert>(1+\gamma/64)r_{B}$, from Claim 4 we know that all points in
$P(v)$ are not in $B$, which is a contradiction. Thus, we can assume that
$\lVert o_{B}-q\rVert\leq(1+\gamma/64)r_{B}$, which leads to two sub cases
discussed in Claim 5: (1) $r^{-}>\gamma r_{B}/512n^{2}d^{2}$, and (2)
$r^{-}\leq\gamma r_{B}/512n^{2}d^{2}$.

For sub-case (1), we first let $d^{(2)}_{min}:=\gamma r_{B}/2048n^{3}d^{3}$.
Then, from Claim 5 we know that the farthest distance between $q$ and a point
in $P\cap\mathcal{B}(o_{B},r^{(2)}_{B})$ is at least $d^{(2)}_{min}$. From
previous discussion and the fact that $\mathcal{B}(o_{B},r^{(2)}_{B})\subset
B(1+\gamma)$, we also know that this farthest distance is at most $d_{max}$.
Let $d^{(2)}_{max}:=d_{max}$. The problem of finding the farthest point
$p^{\prime}_{F}$ to $q$ from all points in
$P\cap\mathcal{B}(o_{B},r^{(2)}_{B})$ satisfies the constraint of
$(r^{(2)}_{B},d^{(2)}_{min},d^{(2)}_{max})$, and is thus solvable by querying
a constrained AIFP data structure. Since the ball range
$\mathcal{B}(o_{B},r^{(2)}_{B})$ only slightly enlarges $B$ and
$\mathcal{B}(q,r^{(2)}_{B})\subset B(1+\gamma)$, with properly selected
approximation factors, it can be shown that the found $p^{\prime}_{F}$ is a
$(\epsilon,\gamma)$-AIFP of $q$ in $B\cap P$. In this case we also have
$d^{(2)}_{max}/d^{(2)}_{min}$ bounded by a polynomial
$2048(4+2\gamma)n^{3}d^{3}/\epsilon$.

For sub-case (2), we let $r^{(3)}_{B}:=d^{(3)}_{max}:=r^{(3)}_{B}$ and
$d^{\prime\prime}_{min}:=r^{(3)}/8nd$. From Claim 5, we know that if $p_{F}\in
P(v)$, $p_{F}$ is also the farthest point to $q$ in $P\cap
B\cap\mathcal{B}(q,r^{(3)}_{B})$. An $(\epsilon,\gamma)$-AIFP of $q$ in $P\cap
B$ can then be found by identifying an AIFP of $q$ in
$P\cap\mathcal{B}(q,r^{(3)}_{B})$. Note that this query satisfies the
constraint of $(r^{(3)}_{B},d^{(3)}_{min},d^{(3)}_{max})$, with
$d^{(3)}_{max}/d^{(3)}_{min}$ bounded by a polynomial of $n$ and $d$.

From the above discussions, we know that given any AIFP query $(B,q)$ (with
radius of $B$ aligned), it is possible to reduce it to a constrained AIFP
query with constraint $(r^{(i)}_{B},d^{(i)}_{min},d^{(i)}_{max})$, which
satisfies the inequality of $d^{(i)}_{min}\leq r^{(i)}_{B}\leq d^{(i)}_{max}$,
$d^{(i)}_{max}/d^{(i)}_{min}$ is bounded by a polynomial
$\mathcal{P}_{gap}(n,d):=2048(4+2\gamma)n^{3}d^{3}/\epsilon$, and
$r^{(i)}_{B}$ is aligned. In the following, we will show how to use multi-
scale construction to build a data structure that supports all such
constrained AIFP queries.

###  4.1 Multi-scale Construction for General AIFP Query

In this subsection, we show how to build a Multi-Scale data structure to
answer general AIFP queries. Our goal is to choose the appropriate parameters
$\Gamma\geq 1$, $0<\lambda<1$ and $\Delta\geq 4nd$ for Algorithm 6 so that for
every AIFP query with constraint $(r^{(i)}_{B},d^{(i)}_{min},d^{(i)}_{max})$,
there exists a bucket $B^{+}_{t}$ whose range
$((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$ wholly covers the interval
$[d^{(i)}_{min},d^{(i)}_{max}]$, and the constrained AIFP data structure built
for the bucket with $d_{min}:=(1+\lambda)^{t}$ and
$d_{max}:=(1+\lambda)^{t+\Gamma+1}$ can be used to answer the query. Note that
we have already defined $\lambda:=\min(\epsilon,\gamma)/512$ and
$\Delta:=4nd$. The remaining task is to determine the value of $\Gamma$.

Observe that $d^{(i)}_{max}/d^{(i)}_{min}$ is bounded by a polynomial
$\mathcal{P}_{gap}(n,d):=2048(4+2\gamma)n^{3}d^{3}/\epsilon$. Let
$\Gamma^{\prime}:=\lceil\log_{1+\lambda}\mathcal{P}_{gap}(n,d)\rceil$, and
$\Gamma_{L}\geq\Gamma^{\prime}$ and $\Gamma_{R}\geq\Gamma^{\prime}$ be integer
parameters to be determined later. Denote by $\Gamma$ the sum of $\Gamma_{L}$
and $\Gamma_{R}$, i.e., $\Gamma:=\Gamma_{L}+\Gamma_{R}$. For every integer
$t$, define $r_{mid}(t):=(1+\lambda)^{t+\Gamma_{L}}$. Therefore, we have
$r_{mid}(t)/(1+\lambda)^{t}\geq(1+\lambda)^{\Gamma_{L}}\geq\mathcal{P}_{gap}(n,d)$
and
$(1+\lambda)^{t+\Gamma+1}/r_{mid}(t)\geq(1+\lambda)^{\Gamma_{R}}\geq\mathcal{P}_{gap}(n,d)$.
For any AIFP query $(B,q)$ with constraint
$(r^{(i)}_{B},d^{(i)}_{min},d^{(i)}_{max})$, it is always possible to find a
bucket $B^{+}_{t}$ such that $r^{(i)}_{B}=r_{mid}(t)$. Clearly, interval
$((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$ wholly covers the interval
$[d^{(i)}_{min},d^{(i)}_{max}]$. If a constrained AIFP data structure is
constructed for $B^{+}_{t}$ with constraint
$((1+\lambda)r_{mid}(t),(1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1})$, it can be
used to answer the AIFP query $(B,q)$. (See Lemma 3.4.)

To summarize the above discussions, we set the parameters of Algorithm 6 as
the following. The algorithm then produces the data structure for
$(\epsilon,\gamma)$-AIFP query. Assume that a real number $0<\delta<1$ is
given and we would like to achieve $1-\delta$ query success probability.

  * •

$\lambda:=\min(\epsilon,\gamma)/512,\Gamma_{L}:=\Gamma^{\prime}+\lceil\log_{1+\lambda}8\rceil,\Gamma_{R}:=\Gamma^{\prime}+\lceil\log_{1+\lambda}8\rceil,\Gamma:=\Gamma_{L}+\Gamma_{R},\Delta:=4nd$.

  * •

Routine $\mathcal{A}$: Given a non-empty bucket $B^{+}_{t}$, $\mathcal{A}$, it
uses Algorithm 1 to creates a constrained $(\lambda/6,\lambda/6)$-AIFP data
structure for point set $re(B^{+}_{t})$ for constraint
$((1+\lambda)r_{mid}(t),(1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1})$, with
success probability at least $1-\delta/4$.

Note that we let
$\Gamma_{L}:=\Gamma_{R}:=\Gamma^{\prime}+\lceil\log_{1+\lambda}8\rceil$. This
allows more gap when fitting the interval $[d^{(i)}_{min},d^{(i)}_{max}]$ in
$((1+\lambda)^{t},(1+\lambda)^{t+\Gamma+1}]$, which is required by Lemma 3.4.

With the multi-scale data structure constructed by Algorithm 6 using the above
parameters, we are able to answer any general AIFP query by reducing it to
constrained AIFP queries with constraints
$(r^{(i)}_{B},d^{(i)}_{min},d^{(i)}_{max})$, $i=1,2,3$. The detailed algorithm
is described as the following Algorithm 7 (for align query ball radius) and
Algorithm 8 (for any radius). Besides the multi-scale structure built using
the parameters $\lambda,\Gamma,\Delta$ and $\mathcal{A}$ as described above, a
$(1+\lambda)$-nearest neighbor data structure from [28], with success
probability $1-\delta/4$ is also used.

Algorithm 7 Query-AIFP-ALIGNED$(B,q)$

Input: A query ball $B$ with $\lambda$-aligned radius $r_{B}$ and centered at
$o_{B}$. A query point $q$.
Output: An $(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

1: If $\lVert q-o_{B}\rVert\geq(3+\gamma)\epsilon^{-1}r_{B}$. Find a
$(1+\gamma/2)$-approximate nearest neighbor $p_{o}\in P$ of $o_{B}$. (Note
this can be done using the $(1+\lambda)$-approximate nearest neighbor data
structure, since $1+\lambda<1+\gamma/2$.) If $p_{o}\in B(1+\gamma/2)$, return
$p_{o}$, otherwise return NULL.

2: Initialize a point set $\mathcal{Q}:=\\{\\}$.

3: Let $t_{1}$ be the integer such that $r_{mid}(t_{1})=r_{B}$. Query the
constrained AIFP data structure for bucket $B^{+}_{t_{1}}$ with $(B,q)$ (using
Algorithm 2). Let $p_{1}$ be the result and put $p_{1}$ into $\mathcal{Q}$.

4: Find $p_{N}\in P$ which is a $(1+\lambda)$-nearest neighbor of $q$ in $P$.
Denote $r_{N}:=\lVert p_{N}-q\rVert$, and put $p_{N}$ into $\mathcal{Q}$.

5: Let $v$ be the lowest (closest to a leaf) node of $T_{P}$ such that $p\in
P(v)$ and $s(v)+r_{N}\leq r_{B}/64\gamma$. (Such $v$ can be found by binary
search on the tree path.) If $v$ does not exist, GOTO step 7.

6: Denote $r^{(2)}_{B}:=[(1+\gamma/16)r_{B}]_{\lambda}$. Let $t_{2}$ be the
integer such that $r_{mid}(t_{2})=r^{(2)}_{B}$. Query the constrained AIFP
data structure for bucket $B^{+}_{t_{2}}$ with
$(\mathcal{B}(o_{B},r^{(2)}_{B}),q)$. Let $p_{2}$ be the result and put
$p_{2}$ into $\mathcal{Q}$.

7: Denote $r^{(3)}_{B}:=[r_{N}+s(v)]_{\lambda}$. Let $t_{3}$ be the integer
such that $r_{mid}(t_{3})=r^{(3)}_{B}$. Query the constrained AIFP data
structure for bucket $B^{+}_{t_{3}}$ with $(\mathcal{B}(q,r^{(3)}_{B}),q)$.
Let $p_{3}$ be the result and put $p_{3}$ into $\mathcal{Q}$.

8: From $\mathcal{Q}$, pick the one that lies in $B(1+\gamma/2)$ and the
distance to $q$ is the farthest. If no such point exists, return NULL.

We then present AIFP query algorithm for $B$ with arbitrary radius. The
algorithm simply enlarges $B$ a little to make the radius aligned, then call
the above Algorithm 7 to handle it.

Algorithm 8 Query-AIFP$(B,q)$

Input: A query ball $B$ with radius $r_{B}$ and center $o_{B}$. A query point
$q$.
Output: An $(\epsilon,\gamma)$-AIFP of $q$ in $P\cap B$.

1: Let $r^{\prime}_{B}:=[r_{B}]_{\lambda}$. Make a query
$(\mathcal{B}(o_{B},r^{\prime}_{B}),q)$ using Algorithm 7, and return the
result.

It is worth noting that since we reduce a general query to at most three
constrained AIFP queries, from Lemma 2.1 and the fact that the ratio
$d_{max}/d_{min}$ satisfies
$d_{max}/d_{min}=(1+\lambda)^{t+\Gamma+1}/(1+\lambda)^{t}=(1+\lambda)^{\Gamma+1}$,
which is bounded by a polynomial of $n,d$, we know that $\log d_{max}/d_{min}$
is $O_{\epsilon,\gamma}(\log nd)$ and the query time is sub-linear. In the
next subsection we provide the detailed analysis of the algorithms and prove
Theorem 1.4.

###  4.2 The Analysis of the AIFP Algorithms

In this subsection, we analyze the algorithms for AIFP and prove Theorem 1.4,
the main result of this paper. We first prove the correctness of Algorithm 7.

######  Lemma 4.1.

With probability at least $1-\delta$, Algorithm 7 returns a
$(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

######  Proof 4.2.

We assume that all the constrained AIFP queries and nearest neighbor queries
are successful. It is easy to see that this happens with probability at least
$1-\delta$.

We decompose the discussion into several cases.

Case 1: $\lVert q-o_{B}\rVert\geq(3+\gamma)\epsilon^{-1}r_{B}$. In this case,
the algorithm return a point $p_{o}\in P\cap B(1+\gamma/2)$ in Step 1, or
return NULL, which only happens when there does not exist points in $P\cap B$
and NULL is a correct answer in this case. From our earlier proof of Claim 2,
we have shown any point in $P\cap B(1+\gamma/2)$ is a
$(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$. This case is proved.

In the following, we assume that $\lVert
q-o_{B}\rVert<(3+\gamma)\epsilon^{-1}r_{B}$. We would show that in each of the
following cases, a correct $(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$
would be put into the set $\mathcal{Q}$. Thus an $(\epsilon,\gamma/2)$-AIFP of
$q$ in $P\cap B$ would be returned in Step 8.

Case 2: The node $v$ in Step 5 does not exists, or $p_{F}\in P\setminus P(v)$
where $p_{F}$ is the farthest point to $q$ in $P\cap B$. From the discussion
in Section 4, query $(B,q)$ satisfies a constraint
$(r^{(1)}_{B},d^{(1)}_{min},d^{(1)}_{max})$ so that it can be answered by the
bucket $B^{+}_{t_{1}}$ in Step 3. From Lemma 3.4, either the point $p_{1}$
obtained in Step 1, or $p_{N}$ obtained in Step 4, would be a
$(2\lambda,2\lambda)$-AIFP of $q$ in $P\cap B$, and is clearly a
$(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

In the following, we exclude the scenario where $p_{N}$ is a
$(2\lambda,2\lambda)$-AIFP of $q$ for a constrained query we make in Step 6 or
7. Indeed this scenario is handled well since $p_{N}$ is already put into
$\mathcal{Q}$.

Case 3: $v$ exists and $p_{F}\in P(v)$. From the discussion in Section 4, one
of the following holds.

  1. (a)

Item 1 of Claim 5 holds, and the query $(\mathcal{B}(o_{B},r^{(2)}_{B}),q)$
satisfies a constraint $(r^{(2)}_{B},d^{(2)}_{min},d^{(2)}_{max})$ so that it
can be answered by the bucket $B^{+}_{t_{2}}$ in Step 6;

  2. (b)

Item 2 of Claim 5 holds, and the query $(\mathcal{B}(q,r^{(3)}_{B}),q)$
satisfies a constraint $(r^{(3)}_{B},d^{(3)}_{min},d^{(3)}_{max})$ so that it
can be answered by the bucket $B^{+}_{t_{3}}$ in Step 7.

For sub-case (a), $p_{2}$ is a $(2\lambda,2\lambda)$-AIFP of $q$ in
$P\cap\mathcal{B}(o_{B},r^{(2)}_{B})$. Thus
$p_{2}\in\mathcal{B}(o_{B},(1+2\lambda)r^{(2)}_{B})$. From some simple
calculation, we know that $(1+2\lambda)r^{(2)}_{B}\leq(1+\gamma/2)r_{B}$. Also
$B\subset\mathcal{B}(o_{B},r^{(2)}_{B})$. Thus $p_{2}$ is a
$(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

Finally, for sub-case (b), $p_{3}$ is a $(2\lambda,2\lambda)$-AIFP of $q$ in
$P\cap\mathcal{B}(q,r^{(3)}_{B})$. Note since $p_{F}\in
P(v)\subset\mathcal{B}(q,r^{(3)}_{B})$, we have $\lVert
q-p_{3}\rVert\geq(1-2\lambda)\lVert q-p_{F}\rVert\geq(1-\epsilon)\lVert
q-p_{F}\rVert$. Also $\lVert
q-p_{3}\rVert\leq(1+2\lambda)r^{(3)}_{B}\leq(1+\gamma)r^{(3)}_{B}$, thus
$p_{3}\in P(v)\subset\mathcal{B}(q,r^{(3)}_{B})\subset B(1+\gamma/2)$. Thus
$p_{3}$ is a $(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

We have proved that in any case, some point in $\mathcal{Q}$ would be a
$(\epsilon,\gamma/2)$ of $q$ in $P\cap B$. The proof is complete.

In the following we prove the correctness of Algorithm 8. We show that
Algorithm 8 returns $(\epsilon,\gamma)$-AIFP of $q$ in $P\cap B$ with
probability at least $1-\delta$.

######  Proof 4.3.

Assume the call to Algorithm 7 is successful, which happens with probability
at least $1-\delta$. Let $p$ be the result of the call to Algorithm 7. Then
$\lVert
o_{B}-p\rVert\leq(1+\gamma/2)r^{\prime}_{B}\leq(1+\gamma/2)(1+\lambda)r_{B}\leq(1+\gamma)r_{B}$.
Also for any $p^{\prime}\in B\cap
P\subset\mathcal{B}(o_{B},r^{\prime}_{B})\cap P$, we have $(1-\epsilon)\lVert
q-p^{\prime}\rVert\leq\lVert q-p\rVert$. Thus $p$ is an
$(\epsilon,\gamma)$-AIFP of $q$ in $P\cap B$.

In the following, we analyze the space and time complexity of the query
scheme.

Pre-processing Time and Space. The AIFP query data structure consists of three
parts: An aggregation tree, a multi-scale data structure and a
$(1+\lambda)$-nearest neighbor data structure. Using the technique in [28], an
aggregation tree takes $O(dn\log^{2}n)$ time to build and takes $O(dn)$ space.
A $(1+\lambda)$-nearest neighbor data structure takes
$O_{c}(dn^{1+1/c}\cdot\text{Polylog}(n))$ time to build and uses
$O_{c}(dn^{1+1/c}\cdot\text{Polylog}(n))$ space, where $c:=1+\lambda$ and the
constant hidden by the $O_{c}(\cdot)$ notation depends only on $c$. For the
multi-scale data structure, note that the total number of nodes in all buckets
is $O_{\lambda}(\Gamma^{2}n\cdot\log(n\Delta))$. From the values of
$\lambda,\Gamma,\Delta$, we know the total number of nodes is
$O_{\epsilon,\gamma}(n\cdot\log n\cdot\log^{2}(nd))$. For each bucket, we
build a constraint $(\lambda/6,\lambda/6)$-AIFP data structure with query
success probability $1-\delta/4$, and we have
$\log(d_{max}/d_{min})=O_{\epsilon,\gamma}(\log nd)$. From Lemma 2.1, the
total preprocessing time and space for these data structures would be
$O_{\epsilon,\gamma}(d\cdot[n\cdot\log
n\cdot\log(nd)]^{1+\rho}\cdot\log\delta^{-1}\cdot\log^{2}nd)$, for some
constant $0<\rho<1$ which depends on $\epsilon,\gamma$. The space/time bound
can be simplified as
$O_{\epsilon,\gamma}(dn^{1+\rho}\cdot\log\delta^{-1}\cdot\log^{5}nd)$. Adding
the complexity for each part together, it is not hard to see the total
space/time complexity for preprocessing is
$O_{\epsilon,\gamma}(dn^{1+\rho}\cdot\log\delta^{-1}\cdot\text{Polylog}(nd))$
for some $0<\rho<1$ which depends on $\epsilon,\gamma$.

Query Time. The query algorithm consists of constant number of nearest
neighbor search and constrained AIFP queries. Each nearest neighbor search
takes $O_{c}(dn^{1/c}\cdot\text{Polylog}(n))$ where $c:=1+\lambda$ and the
constant hidden by the $O_{c}(\cdot)$ notation depends only on $c$. For
constrained AIFP queries, note each bucket has no more than $n$ nodes, from
Lemma 2.1, the query time is
$O_{\epsilon,\gamma}(dn^{\rho}\cdot\log\delta^{-1}\cdot\log(nd))$ for some
constant $0<\rho<1$ which depends on $\epsilon,\gamma$. To summarize, the
query time is
$O_{\epsilon,\gamma}(dn^{\rho}\cdot\log\delta^{-1}\cdot\text{Polylog}(nd))$
for some constant $0<\rho<1$ which depends on $\epsilon,\gamma$.

Combining all the above arguments, Theorem 1.4 is proved.

##  5 MEB Range Aggregate Query

Given any query ball $B$, we find the AMEB of $P\cap B$ using an iterative
algorithm by Badoiu and Clarkson [26]. Their algorithm was originally designed
for finding an approximate MEB for a fixed point set $P$. With careful
analysis we show that their approach, after some modifications, can still be
used to find AMEB in any given range $B$. Briefly speaking, our idea is to
construct a small-size coreset of $P\cap B$. The MEB of the coreset is then a
$(1+\epsilon)$-approximate MEB of $P\cap B$. The algorithm selects the coreset
in an iterative fashion. It starts with an arbitrary point $p$ from $P$. Each
iteration, it performs the following operation to add a point to the coreset:
(1) Compute an (approximate) MEB of the current coreset; (2) Identify the IFP
in $P$ to the center of the current MEB, and add it to the coreset. We show
that after $O_{\epsilon}(\log n)$ iterations, the MEB of the coreset is then a
$(1+\epsilon)$-AMEB of $P\cap B$.

Let $0<\epsilon,\gamma,\delta<1$ be any small constants. Below we discuss the
details of how to use an AIFP data structure built with appropriate parameters
to answer $(\epsilon,\gamma)$-AMEB with success probability at least
$1-\delta$.

Let $\epsilon_{A}:=\gamma_{A}:=\min(\epsilon/18,\gamma/18)$. Define parameters
$\epsilon_{0}=\epsilon^{2}/1600$ and
$\epsilon^{\prime}=\min((1-\epsilon_{0})^{-1}-1,(1-\epsilon^{2}/100)^{-1/2}-1,\epsilon/3)$.
Let $\mathcal{S}$ be a data structure that is capable of answering
$(\epsilon_{A},\gamma_{A})$-AIFP with success probability at least
$1-\delta\epsilon^{2}_{0}/16$. We show that with $\mathcal{S}$ and a
$(1+\gamma_{A})$-nearest neighbor data structure, given any query ball $B$
(with query success probability $1-\delta/2$), the following Algorithm 9
output an AMEB with desired approximation quality and success probability.

The algorithm follows the main idea of the coreset algorithm in [26]: We first
construct an initial coreset $P_{init}$. This can be done by finding an
arbitrary point in $p_{1}\in B(1+\gamma)$, then find another point $p_{2}$
which is an AIFP of $p_{1}$ in $P\cap B$, then let
$P_{init}:=\\{p_{1},p_{2}\\}$. We compute the MEB of $P_{init}$; In each
iteration, we find the approximate farthest point in $P\cap B$ to the center
of the previous MEB, add it to the coreset, and then update the MEB of the
coreset; We output the last found MEB if after one update, the size of MEB
remains roughly the same.

Algorithm 9 AMEB-Query$(B)$

Input: A query ball $B$ centered at $o_{B}$ with radius $r_{B}$.
Output: A ball $B_{MEB}$, which is a $(\epsilon,\gamma)$-AMEB of $P\cap B$.

1: Find a $(1+\gamma_{A})$-nearest neighbor of $o_{B}$ in $P$ and let $p_{a}$
be the result. If $p_{a}\not\in B(1+\gamma_{A})$, return NULL.

2: Find an $(\epsilon_{A},\gamma_{A})$-AIFP of $q$ in $P\cap B$ and let
$p_{b}$ be the result. If $p_{b}$ is NULL, return NULL. Otherwise let
$P_{init}:=\\{p_{a},p_{b}\\}$

3: Initialize a set $P_{core}$ as $P_{init}$. Compute a the MEB of $P_{core}$
(Note currently $P_{core}$ contains only two points so the MEB can be found
easily). Initialize $B_{0}$ to be the computed MEB. Let $c_{0}$ be the center
of $B_{0}$.

4: Let $w=\lceil 4/\epsilon^{2}_{0}\rceil$. For $i$ from $1$ to $w$, do the
following:

  1. 4.1

Try to find an $(\epsilon_{A},\gamma_{A})$-AIFP of $c_{i-1}$ in $B\cap P$ and
denote the result as $p_{i}$. Let $p^{\prime}$ be the farthest point in
$P_{core}$ to $c_{i-1}$. If $p_{i}$ is NULL or $\lVert
c_{i-1}-p_{i}\rVert\leq\lVert c_{i-1}-p^{\prime}\rVert$, return
$B_{i-1}((1-\epsilon_{A})^{-1})$ as the result.

  2. 4.2

Add $p_{i}$ to $P_{core}$.

  3. 4.3

Compute a $(1+\epsilon^{\prime})$ approximate MEB of $P_{core}$ and denote the
result as $B_{i}$. (We use the approximate MEB algorithm in [33].) Let $c_{i}$
be the center of $B_{i}$, and $r_{i}$ be the radius of $B_{i}$.

  4. 4.4

Let $r_{i}$ and $r_{i-1}$ be the radius of $B_{i}$ and $B_{i-1}$,
respectively. If $r_{i}\leq(1+\epsilon_{0})r_{i-1}$, return
$B_{i}(1+\epsilon/3)$ as the result.

5: return $B_{w}(1+\epsilon/3)$ as the result.

We show that the query algorithm output an $(\epsilon,\gamma)$-AMEB of $B\cap
P$ with probability at least $1-\delta$. This proves the correctness of the
algorithm.

######  Proof 5.1.

In the following we assume that the $w$ AIFP queries and the nearest neighbor
query are all successful. By simple calculation, we know that this happens
with probability at least $1-\delta$.

We first define some notations. Let $P_{i}$ denote the set $P_{core}$ after
the $i$-th iteration in Step 2 of Algorithm 9 and $P_{0}=P_{init}$. Let
$P^{\prime}_{i}=P_{i}\cup(P\cap B)$.

Next, we show that the output ball is always an $(\epsilon,\gamma)$-AMEB of
$P$ in $B$. We consider 5 cases, depending on where the algorithm returns: (1)
Step 1, (2) Step 2, (3) Step 4.1, (4) Step 4.4 and (5) Step 5.

Case (1): If $p_{a}$ is a $(1+\gamma_{A})$-nearest neighbor and $p_{a}\not\in
B(1+\gamma_{A})$, this implies $P\cap B=\emptyset$. In this case, NULL is a
valid answer for an AMEB of $P\cap B$.

Case (2): This case also only happens when $P\cap B=\emptyset$, thus NULL is a
valid answer.

Case (3): In this case, for every point $p\in B\cap P$, we have $p\in
B_{i-1}((1-\epsilon_{A})^{-1})$. Also, it is clear that $P^{\prime}_{i}\subset
B(1+\gamma_{A})$. Thus, $B_{i-1}((1-\epsilon_{A})^{-1})$ is a
$((1+\epsilon^{\prime})(1-\epsilon_{A})^{-1})$-approximate MEB of
$P^{\prime}_{i}$, where $P\cap B\subseteq P^{\prime}_{i}\subseteq P\cap
B(1+\gamma_{A})\subseteq P\cap B(1+\gamma)$. By simple calculation, we know
that $B_{i-1}((1-\epsilon_{A})^{-1})$ is a $(\epsilon,\gamma)$-AMEB of $P$ in
$B$.

Case (4): To show this case, we need the following claim. Let $i$ be any
positive integer, and $q_{i}$ be the point on the ray $(c_{i-1},c_{i})$ whose
distance to $c_{i-1}$ is $\lVert
c_{i-1}-q_{i}\rVert=\sqrt{1-(1+\epsilon^{\prime})^{-2}}\,r_{i-1}$. Assume that
$\lVert c_{i-1}-c_{i}\rVert\geq\lVert c_{i-1}-q_{i}\rVert$ (The case where
$\lVert c_{i-1}-c_{i}\rVert<\lVert c_{i-1}-q_{i}\rVert$ will be discussed
later in the proof). Let $H_{i}$ be the hyperplane that passes through $c_{i}$
and is orthogonal to $(c_{i},c_{i-1})$. Let $\mathcal{H}_{i}$ be the closed
half-space bounded by $H_{i}$ and containing $c_{i-1}$. Let
$B^{-}(q_{i},(1+\epsilon^{\prime})^{-1}r_{i-1})$ be an _open_ ball centered at
$q_{i}$ and with radius $(1+\epsilon^{\prime})^{-1}r_{i-1}$.

######  Claim 6.

There exists a point $p^{\prime}_{i-1}\in P_{i-1}$ such that
$p^{\prime}_{i-1}\in\mathcal{H}_{i}\setminus
B^{-}(q_{i},(1+\epsilon^{\prime})^{-1}r_{i})$.

Figure 4: An illustration for Claim 6 and its related arguments.

_Proof of Claim 6._ See Figure 4 for a better understanding of the
configuration. Assume by contradiction that the claim does not hold. Then, it
is not hard to see that $B^{-}(q_{i},(1+\epsilon^{\prime})^{-1}r_{i})$
contains every point in $P_{i-1}$. Since
$B^{-}(q_{i},(1+\epsilon^{\prime})^{-1}r_{i})$ is an open ball, it is possible
to slightly shrink the ball to obtain a closed enclosing ball of $P_{i-1}$
whose radius is strictly smaller than $(1+\epsilon^{\prime})^{-1}r_{i-1}$.
However, since $B_{i-1}$ is a $(1+\epsilon^{\prime})$-approximate MEB of
$P_{i-1}$ of radius $r_{i-1}$, any enclosing ball of $P_{i-1}$ would have a
radius at least $(1+\epsilon^{\prime})^{-1}r_{i-1}$. This is a contradiction,
and thus the claim is true. ∎

We first show that $\lVert c_{i}-c_{i-1}\rVert\leq(\epsilon/10)r_{i-1}$. To
demonstrate this, we first consider the case where $\lVert
c_{i}-c_{i-1}\rVert\geq\sqrt{1-(1+\epsilon^{\prime})^{-2}}\,r_{i-1}=\lVert
c_{i-1}-q_{i}\rVert$ . Let $x_{i}=\lVert c_{i}-c_{i-1}\rVert/r_{i-1}$, and
$p^{\prime}_{i-1}$ be the point that satisfies the above claim. Then, we have

$\displaystyle\lVert p^{\prime}_{i-1}-c_{i}\rVert^{2}$
$\displaystyle\geq(1+\epsilon^{\prime})^{-2}r^{2}_{i-1}+(\lVert
c_{i}-c_{i-1}\rVert-\sqrt{1-(1+\epsilon^{\prime})^{-2}}\,r_{i-1})^{2}$ (1)
$\displaystyle=[(1+\epsilon^{\prime})^{-2}+(x_{i}-\sqrt{1-(1+\epsilon^{\prime})^{-2}})^{2}]r^{2}_{i-1}.$
(2)

Since $B_{i}$ is an approximate MEB of $P_{i}$ and $p^{\prime}_{i-1}\in
P_{i-1}\subset P_{i}$, we have $\lVert p^{\prime}_{i-1}-c_{i}\rVert\leq
r_{i}\leq(1+\epsilon_{0})r_{i-1}$. Combining this with the above inequality,
we get

$(1+\epsilon_{0})^{2}\geq(1+\epsilon^{\prime})^{-2}+(x_{i}-\sqrt{1-(1+\epsilon^{\prime})^{-2}})^{2}.$

From the definition of $\epsilon^{\prime}$ and $\epsilon_{0}$ and some
calculation, we know that
$x_{i}=\sqrt{(1+\epsilon_{0})^{2}-(1+\epsilon^{\prime})^{-2}}+\sqrt{1-(1+\epsilon^{\prime})^{-2}}\leq
2\sqrt{(1+\epsilon_{0})^{2}-(1+\epsilon^{\prime})^{-2}}\leq
2\sqrt{(1+\epsilon_{0})^{2}-(1-\epsilon_{0})^{2}}=4\sqrt{\epsilon_{0}}\leq\epsilon/10$.
This means that $\lVert c_{i}-c_{i-1}\rVert\leq(\epsilon/10)r_{i-1})$ when
$\lVert c_{i}-c_{i-1}\rVert\geq\sqrt{1-(1+\epsilon^{\prime})^{-2}}\,r_{i-1}$.
For the case $\lVert
c_{i}-c_{i-1}\rVert<\sqrt{1-(1+\epsilon^{\prime})^{-2}}\,r_{i-1}=\lVert
c_{i-1}-q\rVert$, from the definition of $\epsilon^{\prime}$, we have
$\epsilon^{\prime}\leq(1-\epsilon^{2}/100)^{-1/2}-1$. Thus,
$\sqrt{1-(1+\epsilon^{\prime})^{-2}}\leq\epsilon/10$. Combining the two cases,
we conclude that $\lVert c_{i}-c_{i-1}\rVert\leq(\epsilon/10)r_{i-1}$.

Let $p$ be an arbitrary point in $P\cap B$. Then, we have $\lVert
p_{i}-c_{i-1}\rVert\geq(1-\epsilon_{A})\lVert p-c_{i-1}\rVert$. Thus, $\lVert
p-c_{i}\rVert\leq\lVert p-c_{i-1}\rVert+\lVert
c_{i}-c_{i-1}\rVert\leq(1-\epsilon_{A})^{-1}\lVert
p_{i}-c_{i-1}\rVert+(\epsilon/10)r_{i-1}\leq(1-\epsilon_{A})^{-1}\lVert
p_{i}-c_{i}\rVert+(1-\epsilon_{A})^{-1}\lVert
c_{i}-c_{i-1}\rVert+(\epsilon/10)r_{i-1}\leq(1-\epsilon_{A})^{-1}r_{i}+(1+(1-\epsilon_{A})^{-1})(\epsilon/10)r_{i-1}$.
Note that since $B_{i}$ is an enclosing ball of $P_{i}$, it is also an
enclosing ball of $P_{i-1}$. From the fact that $B_{i-1}$ is a
$(1+\epsilon^{\prime})$-approximate MEB of $P_{i-1}$, we know that
$r_{i}\geq(1+\epsilon^{\prime})^{-1}r_{i-1}$. Plugging it into the above
inequality, we have $\lVert
p-c_{i}\rVert\leq[(1-\epsilon_{A})^{-1}+(1+(1-\epsilon_{A})^{-1})(1+\epsilon^{\prime})(\epsilon/10)]r_{i}$.
From the definition of $\epsilon_{A},\epsilon^{\prime}$, we get that $\lVert
p-c_{i}\rVert\leq(1+\epsilon/3)r_{i}$. This means that for any $p\in B\cap P$,
$p\in B_{i}(1+\epsilon/3)$. Since $B_{i}$ is a $(1+\epsilon/3)$-approximate
MEB of $P_{i}$, $B_{i}(1+\epsilon/3)$ is a $(1+\epsilon/3)^{2}$-approximate
MEB of $P^{\prime}_{i}=P_{i}\cup(B\cap P)$, and thus a
$(1+\epsilon)$-approximate MEB. Clearly, we have $B\cap P\subseteq
P^{\prime}_{i}\subseteq B(1+\gamma)\cap P$. Therefore, $B_{i}(1+\epsilon/3)$
is a $(\epsilon,\gamma)$-AMEB of $P$ in $B$.

Case (5): Note that for any $i=0,1,\ldots,w-1$, we have
$r_{i+1}\geq(1+\epsilon_{0})r_{i}$. Also note $w=\lceil
4/\epsilon^{2}_{0}\rceil$. Thus we have
$r_{w}\geq(1+\epsilon_{0})^{w}r_{0}\geq 4r_{0}/\epsilon_{0}$. For any
$p^{\prime}\in B\cap P$, we claim that $p^{\prime}\in B_{w}(1+\epsilon/3)$. To
see this, note clearly $r_{0}=\lVert p_{a}-p_{b}\rVert/2$, and
$(1-\epsilon_{A})\lVert p^{\prime}-p\rVert\leq\lVert p_{a}-p_{b}\rVert$. Thus
$\lVert p^{\prime}-p\rVert\leq
2(1-\epsilon_{A})^{-1}r_{0}\leq((1-\epsilon_{A})^{-1}/2)\epsilon_{0}r_{w}\leq\epsilon_{0}r_{w}$.
Thus $p^{\prime}\in B_{w}(1+\epsilon_{0})\subset B_{w}(1+\epsilon/3)$.

Since $B_{w}$ is a $(1+\epsilon^{\prime})$-approximate enclosing ball of a
subset $P^{\prime}$ of $P\cap B(1+\gamma_{A})\subset P\cap B(1+\gamma)$, by
simple calculation, we know that $B_{w}(1+\epsilon/3)$ is an
$(1+\epsilon)$-approximate MEB of $P^{\prime}$. Since $P\cap B\subset
B_{w}(1+\epsilon/3)$, we know $B_{w}(1+\epsilon/3)$ is an
$(1+\epsilon)$-approximate MEB of $P^{\prime}\cup(P\cap B)$, and clearly
$P\cap B\subset P^{\prime}\cup(P\cap B)\subset P\cap B(1+\gamma)$. Thus
$B_{w}(1+\epsilon/3)$ is an $(\epsilon,\gamma)$-AMEB of $B\cap P$.

Complexity Analysis. The nearest neighbor data structure takes
$O_{\epsilon,\gamma}(dn^{1+\rho})$ time to build where $0<\rho<1$ depends on
$\epsilon,\gamma$. Algorithm 9 makes one nearest neighbor search (which takes
$O_{\epsilon,\gamma}(dn^{\rho})$ time), and $O_{\epsilon,\gamma}(1)$ AIFP
queries. Combining the result of AIFP query (Theorem 1.4), Theorem 1.5
follows.

## References

  * [1] Pankaj K Agarwal, Jeff Erickson, et al.  Geometric range searching and its relatives.  Contemporary Mathematics, 223:1–56, 1999.
  * [2] Yufei Tao, Xiaokui Xiao, and Reynold Cheng.  Range search on multidimensional uncertain data.  ACM Transactions on Database Systems (TODS), 32(3):15–es, 2007\.
  * [3] Mikkel Abrahamsen, Mark de Berg, Kevin Buchin, Mehran Mehr, and Ali D Mehrabi.  Range-clustering queries.  arXiv preprint arXiv:1705.06242, 2017.
  * [4] Pankaj K Agarwal, Lars Arge, Sathish Govindarajan, Jun Yang, and Ke Yi.  Efficient external memory structures for range-aggregate queries.  Computational Geometry, 46(3):358–370, 2013.
  * [5] Sunil Arya, David M Mount, and Eunhui Park.  Approximate geometric mst range queries.  In 31st International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015.
  * [6] Peter Brass, Christian Knauer, Chan-Su Shin, Michiel Smid, and Ivo Vigan.  Range-aggregate queries for geometric extent problems.  In Proceedings of the Nineteenth Computing: The Australasian Theory Symposium-Volume 141, pages 3–10, 2013.
  * [7] Prosenjit Gupta, Ravi Janardan, Yokesh Kumar, and Michiel Smid.  Data structures for range-aggregate extent queries.  Computational Geometry, 47(2):329–347, 2014.
  * [8] Sankalp Khare, Jatin Agarwal, Nadeem Moidu, and Kannan Srinathan.  Improved bounds for smallest enclosing disk range queries.  In CCCG. Citeseer, 2014.
  * [9] Zhe Li, Tsz Nam Chan, Man Lung Yiu, and Christian S Jensen.  Polyfit: Polynomial-based indexing approach for fast approximate range aggregate queries.  arXiv preprint arXiv:2003.08031, 2020.
  * [10] Yakov Nekrich and Michiel HM Smid.  Approximating range-aggregate queries using coresets.  In CCCG, pages 253–256, 2010.
  * [11] Saladi Rahul, Haritha Bellam, Prosenjit Gupta, and Krishnan Rajan.  Range aggregate structures for colored geometric objects.  In CCCG, pages 249–252, 2010.
  * [12] Saladi Rahul, Ananda Swarup Das, KS Rajan, and Kannan Srinathan.  Range-aggregate queries involving geometric aggregation operations.  In International Workshop on Algorithms and Computation, pages 122–133. Springer, 2011.
  * [13] Xiaochun Yun, Guangjun Wu, Guangyan Zhang, Keqin Li, and Shupeng Wang.  Fastraq: A fast approach to range-aggregate queries in big data environments.  IEEE Transactions on Cloud Computing, 3(2):206–218, 2014.
  * [14] Ching-Tien Ho, Rakesh Agrawal, Nimrod Megiddo, and Ramakrishnan Srikant.  Range queries in olap data cubes.  ACM SIGMOD Record, 26(2):73–88, 1997.
  * [15] Jeffrey Scott Vitter and Min Wang.  Approximate computation of multidimensional aggregates of sparse data using wavelets.  Acm Sigmod Record, 28(2):193–204, 1999.
  * [16] Eugene Wu and Samuel Madden.  Scorpion: Explaining away outliers in aggregate queries.  2013\.
  * [17] Mayur Datar, Nicole Immorlica, Piotr Indyk, and Vahab S Mirrokni.  Locality-sensitive hashing scheme based on p-stable distributions.  In Proceedings of the twentieth annual symposium on Computational geometry, pages 253–262, 2004.
  * [18] Ryan R Curtin and Andrew B Gardner.  Fast approximate furthest neighbors with data-dependent candidate selection.  In International Conference on Similarity Search and Applications, pages 221–235. Springer, 2016.
  * [19] Qiang Huang, Jianlin Feng, and Qiong Fang.  Reverse query-aware locality-sensitive hashing for high-dimensional furthest neighbor search.  In 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pages 167–170. IEEE, 2017.
  * [20] Piotr Indyk.  Better algorithms for high-dimensional proximity problems via asymmetric embeddings.  In Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, pages 539–545, 2003.
  * [21] Rasmus Pagh, Francesco Silvestri, Johan Sivertsen, and Matthew Skala.  Approximate furthest neighbor in high dimensions.  In International Conference on Similarity Search and Applications, pages 3–14. Springer, 2015.
  * [22] Jie Xue.  Colored range closest-pair problem under general distance functions.  In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 373–390. SIAM, 2019.
  * [23] Jie Xue, Yuan Li, and Ravi Janardan.  Approximate range closest-pair queries.  Computational Geometry, 90:101654, 2020.
  * [24] Sofiane Abbar, Sihem Amer-Yahia, Piotr Indyk, Sepideh Mahabadi, and Kasturi R Varadarajan.  Diverse near neighbor problem.  In Proceedings of the twenty-ninth annual symposium on Computational geometry, pages 207–214, 2013.
  * [25] Martin Aumüller, Sariel Har-Peled, Sepideh Mahabadi, Rasmus Pagh, and Francesco Silvestri.  Sampling a near neighbor in high dimensions–who is the fairest of them all?  arXiv preprint arXiv:2101.10905, 2021.
  * [26] Mihai Badoiu and Kenneth L Clarkson.  Smaller core-sets for balls.  In SODA, volume 3, pages 801–802, 2003.
  * [27] Martin Aumüller, Tobias Christiani, Rasmus Pagh, and Francesco Silvestri.  Distance-sensitive hashing.  In Proceedings of the 37th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, pages 89–104, 2018.
  * [28] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani.  Approximate nearest neighbor: Towards removing the curse of dimensionality.  Theory of computing, 8(1):321–350, 2012.
  * [29] Alexandr Andoni, Piotr Indyk, Huy L Nguyen, and Ilya Razenshteyn.  Beyond locality-sensitive hashing.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1018–1028. SIAM, 2014.
  * [30] Michael Mitzenmacher and Eli Upfal.  Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis.  Cambridge university press, 2017.
  * [31] Ziyun Huang, Hu Ding, and Jinhui Xu.  A faster algorithm for truth discovery via range cover.  Algorithmica, 81(10):4118–4133, 2019.
  * [32] Sariel Har-Peled.  Geometric approximation algorithms.  Number 173. American Mathematical Soc., 2011.
  * [33] Piyush Kumar, Joseph SB Mitchell, and E Alper Yıldırım.  Computing core-sets and approximate smallest enclosing hyperspheres in high dimensions.  algorithms, 22:26.

##  Appendix A Appendix

###  A.1 Proof of Lemma 2.3

######  Proof A.1.

In the following we assume that all the BD queries are successful. By simple
calculation, we know that this happens with probability at least $1-\delta$.

We first note that the return value would not be NULL if $(B,q)$ satisfies the
constraint $(r_{B},d_{min},d_{max})$, since this only happens when the BD
query $(B,B_{out,0})$ returns a NULL, which implies there is no point in $P$
that lies in $B\setminus B_{out,0}$. This means there is no point in $P\cap B$
whose distance to $q$ is at least $r_{0}=d_{min}$, contradicting our
assumption.

Next we consider the case where the algorithm returns at Step 3. Clearly
$p_{ans}\in B(1+\xi)\setminus B_{out,m}((1+\xi)^{-1})$. Thus $\lVert
p_{ans}-q\rVert\geq d_{max}/(1+\xi)$. Note for any $p\in P\cap B$, $\lVert
q-p\rVert\leq d_{max}$ from the constraint. The proof of this case is
therefore complete.

Finally we consider the case that the algorithm returns at Step 2. There
exists $i$ such that $p_{ans}\in B(1+\xi)\setminus B_{out,i}((1+\xi)^{-1})$,
and the BD query $(B,B_{out,i+1})$ returns a NULL. We know that there does not
exist a point in $P\cap B\setminus B_{out,i+1}$. Thus, let $p$ be any point in
$P\cap B$, we have $p\in B_{out,i+1}$, which means $\lVert q-p\rVert\leq
r_{i+1}=(1+\xi)r_{i}$. Since $p_{ans}\not\in B_{out,i}((1+\xi)^{-1})$, we have
$\lVert p_{ans}-q\rVert\geq(1+\xi)^{-1}r_{i}$. Thus $\lVert
p_{ans}-q\rVert\geq(1+\xi)^{-2}\lVert p-q\rVert\geq(1-\epsilon)\lVert
p-q\rVert$. This completes the proof.

###  A.2 Missing Proofs in Section 2.1

The following is the proof of Lemma 2.7.

######  Proof A.2.

In order for $G_{p}$ to be examined, for every $j=1,2,\ldots,b$, the following
two (independent) events have to happen: (1)
$\text{COM}(\textsc{lab}_{in}(p,j),\textsc{lab}_{in}(o_{in},j))$ $\geq
t_{1}\wedge\text{COM}(\textsc{lab}_{out}(p,j)$,
$\textsc{lab}_{out}(o_{out},j))\geq t_{2}$, which happens with probability at
least $4/9$, and (2) $\textsc{lab}_{in}(p,j)=\textsc{lab}^{\prime}_{in}(j)$
and $\textsc{lab}_{out}(p,j)=\textsc{lab}^{\prime}_{out}(j)$, which happens
with probability $2^{-2a}$. Thus, the probability of the above two events
happen is $[(4/9)(2^{-2a})]^{b}$. This proves the lemma for $G_{p}$. The case
for $G_{q}$ can also be proved in a similar manner.

With the above two lemmas, we can obtain the following lemma. The argument has
some similarity with some proofs in [28] for near neighbor search with LSH.

The following is the proof of Lemma 2.8.

######  Proof A.3.

For ease of analysis, we consider a modified version of Algorithm 4: we assume
that the algorithm does not terminate after $3c$ points are examined, and it
does not return even after a point in $B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1})$ is found. Consider the following event:

  * •

$E$: Among the first $3c$ examined points, there exists one point that is in
$P\cap(B_{in}(1+\xi)\setminus B_{out}((1+\xi)^{-1}))$.

We prove that event $E$ happens with probability at least $1/4$. The lemma
will then follows.

Let $p\in P$ be a point that lies in $B_{in}\setminus B_{out}$. Consider the
following 2 events:

  * •

$E_{1}$: $p$ is examined.

  * •

$E_{2}$: The number of points $q\not\in(B_{in}(1+\xi)\setminus
B_{out}((1+\xi)^{-1}))$ such that $q$ is examined is strictly less than $3c$.

If both of the events occur, then clearly $E$ happens. Thus, we only need to
prove that with probability $1/4$ both $E_{1}$ and $E_{2}$ happen.

We first consider $E_{1}$. Note that for every $k=1,2,\ldots,c$, the
probability that $p$ is examined in the for loop of Step 1 of Algorithm 4 is
at least $(P^{\prime\prime}_{1})^{b}$. Note that

$(P^{\prime\prime}_{1})^{b}\geq(P^{\prime\prime}_{1})^{1+\log_{1/P^{\prime\prime}_{2}}n}=P^{\prime\prime}_{1}n^{-\rho}.$

The probability that $E_{1}$ does not happen is at most
$(1-(P^{\prime\prime}_{1})^{b})^{c}\leq(1-P^{\prime\prime}_{1}n^{-\rho})^{c}\leq(1-P^{\prime\prime}_{1}n^{-\rho})^{n^{\rho}/P^{\prime\prime}_{1}}\leq
1/e$. Thus, we have $\text{PR}[E_{1}]\geq 1-1/e$.

Next, we consider event $E_{2}$. Let $q$ be any point that lies outside of
$B_{in}(1+\xi)\setminus B_{out}((1+\xi)^{-1})$. We call such $q$ a “bad”
point. For any bad point $q$, the probability that $q$ is examined in the for
loop of Step 1 of Algorithm 4 is at most $(P^{\prime\prime}_{2})^{b}\leq 1/n$.
Thus, the expected number of examined bad point in each iteration of the loop
is at most 1. Let $X$ denote the number of examined bad points after all the
$c$ iterations. Then, we have $E[X]\leq c$. By Markov’s inequality, we get
$\text{Pr}[X\geq 3c]\leq 1/3$. Hence, $\text{Pr}[E_{2}]=\text{Pr}[X<3c]\geq
2/3$.

The probability that both $E_{1}$ and $E_{2}$ happen is thus no less than
$(1-1/e)+2/3-1\geq 1/4$. This completes the proof.

In the following we analyze the space/time complexity of the BD query scheme
and prove Lemma 2.2. We first consider the process of creating the BD data
structure in Algorithm 3. The algorithm creates $c$ groups of buckets. For
each group, every point in $P$ is hashed into one bucket. In order to create
these buckets, we sample a total of $2abc$ hash functions from LSH families
$\mathcal{H}_{in}$ and $\mathcal{H}_{out}$, and apply them to every point in
$P$ to determine the buckets it belongs to. The total running time for this is
$O(dabcn)$. Since $a=O_{\xi}(1),b=O_{\xi}(\log n)$ and $c=O_{\xi}(n^{\rho})$,
where $\rho$ and the constant hidden in the big-O notation depends only on
$\xi$. Thus, the preprocessing time and the space complexity of the
$\xi$-error BD query data structure is $O_{\xi}(dn^{1+\rho}\log n)$.

Next, we analyze the query process, i.e., Algorithm 4. The main loop has at
most $c$ iterations. In each iteration, we first determine the bucket to
examine, which takes $O(dab)$ time to compute the labels. Also, note that the
process will terminate after $3c$ points are examined. Thus, the total running
time for the query algorithm is $O(abcd)$, which is $O_{\xi}(dn^{\rho}\log
n)$.

Note that it is easy to see that a BD query data structure with query success
rate $1-\delta$ can be obtained by combining $O(\log\delta^{-1})$ BD
structures with query success rate $1/4$. Lemma 2.2 then follows, which
concludes this subsection.

###  A.3 Missing Proofs in Section 4

Proof of Claim 2.

######  Proof A.4.

Indeed, we will prove a slightly stronger version of Claim 2: If $\lVert
q-o_{B}\rVert\geq(3+\gamma)\epsilon^{-1}r_{B}$, then any point $p$ in
$B(1+\gamma/2)$ is an $(\epsilon,\gamma/2)$-AIFP of $q$ in $P\cap B$.

Let $p^{\prime}$ be arbitrary point in $P\cap B$, then $\lVert
p^{\prime}-p\rVert\leq(2+\gamma)r_{B}$. Note $\lVert
p^{\prime}-q\rVert\geq\lVert q-o_{B}\rVert-\lVert
p^{\prime}-o_{B}\rVert\geq(3+\gamma)\epsilon^{-1}r_{B}-r_{B}\geq(2+\gamma)\epsilon^{-1}r_{B}$.
Therefore $\lVert p^{\prime}-p\rVert\leq\epsilon\lVert p^{\prime}-q\rVert$.
Thus $\lVert p-q\rVert\geq\lVert p^{\prime}-q\rVert-\lVert
p^{\prime}-p\rVert\geq(1-\epsilon)\lVert p^{\prime}-q\rVert$. Since $p$ is in
$B(1+\gamma/2)$, we conclude that $p$ is an $(\epsilon,\gamma/2)$-AIFP of $q$
in $P\cap B$.

Proof of Claim 3.

######  Proof A.5.

If $v$ does not exists, then $r_{N}>\gamma r_{B}/64$. Since $p_{N}$ is a
2-nearest neighbor, for any $p^{\prime}\in P$, we have $\lVert
p^{\prime}-q\rVert\geq r_{N}/2$. Thus $\lVert p^{\prime}-q\rVert>\gamma
r_{B}/128$, and the claim follows easily in this case.

In the following, let $v_{p}$ denote the parent node of $v$ (if $v_{p}$ does
not exists, _i.e._ $v$ is the root of $T_{P}$, then the claim is trivial).
Then from the definition of $v$, we know that $s(v_{p})+r_{N}\geq\gamma
r_{B}/64$. From the property of $T_{P}$, for any $p_{out}\in P\setminus P(v)$,
$s(v_{p})\leq\lVert p_{out}-q\rVert nd$. Thus $\lVert p_{out}-q\rVert
nd+r_{N}\geq\gamma r_{B}/64$. Therefore, either $r_{N}\geq\gamma r_{B}/128$ or
$\lVert p_{out}-q\rVert nd\geq\gamma r_{B}/128$. Note that if $r_{N}\geq\gamma
r_{B}/128$, then the claim follows easily, since $p_{N}$ is a 2-nearest
neighbor of $q$ in $P$. So we assume $\lVert p_{out}-q\rVert nd\geq\gamma
r_{B}/128$, which gives us $\lVert p_{out}-q\rVert\geq\gamma r_{B}/128nd$. The
proof is complete.

Proof of Claim 4

######  Proof A.6.

Assume $\lVert o_{B}-q\rVert>(1+\gamma/64)r_{B}=r_{B}+\gamma r_{B}/64$. Note
$s(v)+r_{N}\leq\gamma r_{B}/64$, and $s(v)$ is an upper bound of the diameter
of $P(v)$, then for any $p\in P(v)$, we have $\lVert p-q\rVert\leq\gamma
r_{B}/64$. Therefore $p\not\in B$.

Proof of Claim 5

######  Proof A.7.

We first consider case $r^{-}=r_{N}+s(v)>\gamma r_{B}/512n^{2}d^{2}$. Then
either (a) $r_{N}>\gamma r_{B}/1024n^{2}d^{2}$, or (b) $s(v)>\gamma
r_{B}/1024n^{2}d^{2}$. For case (a), let $p_{1}$ be arbitrary point in $P\cap
B\subset P\cap\mathcal{B}(o_{B},r^{(2)}_{B})$, since $p_{N}$ is a 2-nearest
neighbor, we have $\lVert p_{1}-q\rVert\geq r_{N}/2\geq\gamma
r_{B}/2048n^{2}d^{2}$. For case (b), note $s(v)$ is not larger than $nd$ times
the diameter of $P(v)$, thus there exists $p_{1},p_{2}\in P(v)$, such that
$s(v)\leq\lVert p_{1}-p_{2}\rVert nd$. Thus $\lVert
p_{1}-p_{2}\rVert\geq\gamma r_{B}/1024n^{3}d^{3}$. Thus at least one of
$p_{1}$ or $p_{2}$, just say $p_{1}$, would satisfy $\lVert
p_{1}-q\rVert\geq\gamma r_{B}/2048n^{3}d^{3}$. Also
$p_{1}\in\mathcal{B}(o_{B},r^{(2)}_{B})$. In fact, for any point
$p^{\prime}\in P(v)$, $\lVert o_{B}-p^{\prime}\rVert\leq\lVert
o_{B}-q\rVert+\lVert
q-p^{\prime}\rVert\leq(1+\gamma/64)r_{B}+(r_{N}+s(v))\leq(1+\gamma/64)r_{B}+\gamma
r_{B}/64=(1+\gamma/32)r_{B}$, which implies
$p^{\prime}\in\mathcal{B}(o_{B},r^{(2)}_{B})$. We have proved item 1 of the
claim.

Now assume $r^{-}=r_{N}+s(v)\leq\gamma r_{B}/512n^{2}d^{2}$. For every $p\in
P(v)$, we have $\lVert p-q\rVert\leq r_{N}+s(v)=r^{-}\leq[r^{-}]_{\lambda}$,
thus $p\in\mathcal{B}(o_{B},r^{(3)}_{B})$. Also from Claim 3, for any
$p_{out}\in P\setminus P(v)$, we have $\lVert q-p_{out}\rVert\geq\gamma
r_{B}/256nd$. From this, it is not hard to see by calculation that $p_{out}$
lies outside of $p\in\mathcal{B}(o_{B},(1+\gamma)r^{(3)}_{B})$.

Note clearly $s(v)+r_{N}=r^{-}\geq(1+\lambda)^{-1}r^{(3)}_{B}\geq
r^{(3)}_{B}/2$. If $r_{N}\geq r^{(3)}_{B}/4$, then we have $\lVert
q-p_{N}\rVert=r_{N}\leq r^{(3)}_{B}/4$ and $p_{N}\in P(v)$, and the claim is
proved in this case. Assume $r_{N}<r^{(3)}_{B}/4$, then $s(v)\geq
r^{(3)}_{B}/4$. Now let $p_{1},p_{2}\in P(v)$ such that $\lVert
p_{1}-p_{2}\rVert$ is the diameter of $P(v)$. Thus $r^{(3)}_{B}/4\leq s(v)\leq
nd\lVert p_{1}-p_{2}\rVert$. Thus $\lVert p_{1}-p_{2}\rVert\geq
r^{(3)}_{B}/4nd$. Then for at least one of $p_{1},p_{2}$, its distance to $q$
is at least $r^{(3)}_{B}/8nd$. The proof is complete.

For any $p^{\prime}\in\mathcal{B}(o_{B},r^{(3)}_{B})$, $\lVert
o_{B}-p^{\prime}\rVert\leq\lVert o_{B}-q\rVert+\lVert
q-p^{\prime}\rVert\leq(1+\gamma/64)r_{B}+\gamma
r_{B}/256n^{2}d^{2}\leq(1+\gamma/32)r_{B}$. Thus
$\mathcal{B}(o_{B},r^{(3)}_{B})\subset B(1+\gamma/32)$.