# Sub-quadratic $(1+\epsilon)$-approximate Euclidean Spanners, with
Applications

Alexandr Andoni Hengjie Zhang<EMAIL_ADDRESS>Columbia
<EMAIL_ADDRESS>Columbia University.

###### Abstract

We study graph spanners for point-set in the high-dimensional Euclidean space.
On the one hand, we prove that spanners with stretch $<\sqrt{2}$ and
subquadratic size are not possible, even if we add Steiner points. On the
other hand, if we add extra nodes to the graph (non-metric Steiner points),
then we can obtain $(1+\epsilon)$-approximate spanners of subquadratic size.
We show how to construct a spanner of size $n^{2-\Omega(\epsilon^{3})}$, as
well as a directed version of the spanner of size
$n^{2-\Omega(\epsilon^{2})}$.

We use our directed spanner to obtain an algorithm for computing
$(1+\epsilon)$-approximation to Earth-Mover Distance (optimal transport)
between two sets of size $n$ in time $n^{2-\Omega(\epsilon^{2})}$.

##  1 Introduction

A spanner for a metric defined by the graph $G$ is a subgraph $H$ such that
all shortest path distances in $H$ approximate shortest path distances in $G$
up to some approximation $\alpha$. Originally introduced in [PS89], the notion
has been very influential in theory and practice — see, for example, the
recent survey [ABS+20] and earlier surveys [Epp99, Zwi01]. The classic result
is that, for any integer $k\geq 1$, for any weighted graph $G$, one can
construct a spanner of size $O(n^{1+1/k})$ approximating all distances up to
factor $2k-1$ [PS89], termed stretch. This is tight under the Erdös girth
conjecture [Erd63].

Graph spanners have been studied in a number of settings and variants. While
we refer the reader to the survey [ABS+20] for the vast list of relevant
papers, we highlight that there are a number of parameters/versions of
spanners considered: approximation (e.g., multiplicative, additive, and
others), which pairs to preserve, properties of the graph $G$, computation
time, data structures (distance oracles), etc.

An almost disjoint line of research concerns geometric spanners, where the
graph $G$ is defined implicitly as the pairwise distance in some metric $M$;
introduced in [Che86] even before spanners where defined. In particular, here
$G$ is a complete graph, where each pair of nodes is connected with an edge
with weight equal to their distance. The classic results here show that an
$n$-point metric in the Euclidean space $\mathbb{R}^{d}$ admits a
$(1+\epsilon)$-approximation spanner of size $O(n\cdot\epsilon^{-d+1})$
[Cla87, Kei88, KG92, ADD+93]; see also the survey [NS07].

More recent progress [LS22, BT22] showed tightness of the bound
$n\epsilon^{-d+1}$, but also that Steiner spanners can improve the size to
$O(n\epsilon^{\tfrac{-d+1}{2}})$. A Steiner spanner is a graph whose nodes are
the pointset $P\subset\mathbb{R}^{d}$ together with some extra Steiner points
$\in\mathbb{R}^{d}$. Whenever an edge is added to the spanner, its weight is
the direct distance between the corresponding points (so that no pair is
shortcut).

In contrast to the two extremely well-studied settings from above, the high-
dimensional geometric spanners have surprisingly received much less attention.
In particular, we are aware of only one (theoretical) result: [HPIS13] who
obtained $c$-spanner of size $O(n^{1+O(1/c^{2})})$ for any $c\geq 3.4$. This
is despite the ubiquity of high-dimensional datasets and the fact that many
(massive) graphs are actually “similarity graphs” 111While similarity graph is
a bit different from the aforementioned complete graph — e.g., the edges are
only for pairs of points at distance $\leq r$ — the tools from here apply to
such graphs nonetheless., obtained by connecting close points of some dataset
$P\in\mathbb{R}^{d}$ — subsequently used for various clustering applications;
see recent [DEL+22] and references therein. Indeed, the spanner from [HPIS13]
has been implemented in [CHJ+22], yielding orders of magnitude speed up in
graph building, without affecting down-the-stream clustering which leverages
the spanner only.

To put our lack of understanding into perspective, we don’t even know if we
can obtain subquadratic-size spanners for approximation $c\leq 3.4$.

###  1.1 Our contributions

We build new high-dimensional geometric spanners in the $1+\epsilon$
approximation regime, asking the following main question:

######  Question 1.1.

Do there exist spanners for high-dimensional Euclidean pointset with
$1+\epsilon$ approximation and subquadratic size?

From now on, we assume we have an $n$-point dataset $P\in\mathbb{R}^{d}$ under
the Euclidean distance, where $d\gg\log n$. For a graph $H$, we use
$\mathrm{d}_{H}(p,q)$ to denote the shortest path distance between $p$ to $q$
in $H$. We also let $\Delta$ be the aspect ratio of $P$:
$\Delta=\tfrac{\max_{p,q\in P}\|p-q\|_{2}}{\min_{p,q\in P,p\neq
q}\|p-q\|_{2}}$.

#### Lower bound for spanners.

We first give indication that it is impossible to obtain $(1+\epsilon)$
approximation with a sub-quadratic-sized spanner even if we allow Steiner
points. In particular, we prove the following two lower bounds for the Hamming
metric and Euclidean metric, respectively.

######  Theorem 1.2 (See Section 2.1).

For any $\epsilon>0$, there exists a dataset $P\subset\\{0,1\\}^{d}$ such that
the following holds. Fix a graph $H$ with vertices identified with $P$, such
that for any $p,q\in P$,

$\|p-q\|_{1}\leq\mathrm{d}_{H}(p,q)<(2-\epsilon)\cdot\|p-q\|_{1}.$

Then $H$ must have $\Omega(n^{2}\epsilon^{4})$ edges. This remains true even
if $H$ contains Steiner vertices corresponding to points in $\\{0,1\\}^{d}$.

######  Theorem 1.3 (See Section 2.2).

For any $\epsilon>0$, there exists a dataset $P\subset S^{d-1}(0,1)$ such that
the following holds. Fix a graph $H$ with vertices identified with $P$, such
that for any $p,q\in P$,

$\|p-q\|_{2}\leq\mathrm{d}_{H}(p,q)<(\sqrt{2}-\epsilon)\cdot\|p-q\|_{2}.$

Then $H$ must have $\Omega(n^{2}\epsilon^{4}/\log^{2}n)$ edges. This remains
true even if $H$ contains Steiner vertices corresponding to points in
$\mathbb{R}^{d}$.

#### Spanners with non-metric Steiner nodes.

Next, we show that if we consider a more general class of Steiner spanners,
where we allow graph nodes that do not correspond to points
$\in\mathbb{R}^{d}$, we can indeed obtain $(1+\epsilon)$-spanners of
subquadratic size, answering positively the question from above. We refer to
such spanners as non-metric Steiner spanners.

Furthermore, we distinguish two types of non-metric Steiner spanners:
undirected, and directed. In particular, a directed spanner $H$ for sets $P,Q$
with stretch $c>1$ is a directed graph with vertex-set $P\cup Q\cup S$,
satisfying for all $p\in P,q\in Q$:

$\|p-q\|\leq\vec{\mathrm{d}}_{H}(p,q)\leq c\|p-q\|,$

where $\vec{\mathrm{d}}_{H}(p,q)$ as the shortest path from $p\in P$ to $q\in
Q$. When we have one dataset $P$, we take $Q$ to be a copy of $P$. Note that
directed spanner only makes sense for non-metric Steiner version.

######  Theorem 1.4 (See Section 3).

Fix $\epsilon\in(0,1)$. For any dataset $P\in\mathbb{R}^{d}$, there exists a
directed graph $H$ on vertices $P\cup S$, such that for any $p,q\in P$,

$\|p-q\|_{2}\leq\vec{\mathrm{d}}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

Furthermore, the number of edges of $H$, the size of $S$, and the construction
time are all bounded by $O(n^{2-\Omega(\epsilon^{2})}\log\Delta)$, where
$\Delta$ is the aspect ratio of $P$.

While the directed spanner turns out to be already sufficient for our
application below, there other applications which may require an undirected
graph (as many graph problems are easier for undirected graphs). Thus, we also
show that one can construct an undirected spanner, albeit the parameters are
less efficient than for the directed case.

######  Theorem 1.5 (See Section 4).

Fix $\epsilon\in(0,1)$. For any dataset $P\in\mathbb{R}^{d}$, we can construct
an undirected graph $H$ on vertices $P\cup S$, such that for any $p,q\in P$,

$\|p-q\|_{2}\leq\mathrm{d}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

Furthermore, the construction time, the number of edges of $H$ and the size of
$S$ are bounded by $O(n^{2-\Omega(\epsilon^{3})}\log\Delta)$, where $\Delta$
is the aspect ratio of $P$.

#### Sub-quadratic algorithms for the Earth-Mover Distance in high dimensions
problem

We highlight one concrete algorithmic application of our spanner construction.
In particular, we consider the problem of Earth-Mover Distance in the high-
dimensional spaces: given two $n$-points sets $A,B\subset\mathbb{R}^{d}$,
compute the smallest cost bi-chromatic matching
$\operatorname{argmin}_{\pi:A\to B}\tfrac{1}{n}\sum_{a\in A}\|a-\pi(a)\|$
where $\pi$ ranges over all permutations. In different communities, the EMD
problem is also termed optimal transport, Wasserstein distance, Monge-
Kantarovich, and others.222Formally, all these are defined over distributions
over $n$ points, equivalently weighted pointsets. All our results apply to the
weighted version as well, and hence we ignore the difference for simplicity of
presentation.

The basic problem is to compute the (near-) optimal $\pi$ efficiently. When
dimension $d$ is small, a long progression of results, starting from [Vai89]
and culminating in [KNP19] yielded an $(1+\epsilon)$-approximate algorithm
running in time $\widetilde{O}(n)\cdot\epsilon^{O(d)}$.

Another line of research concerns the general metric (or cost) setting, i.e.,
more general than the Euclidean setting. Here, the best possible runtime is
$\sim n^{2}$, which is necessary in general. One approach uses Sinkhorn
iteration algorithm to obtain additive error of $\epsilon\max_{p,q\in
A,B}\|p-q\|$ [Cut13, ANWR17]. A different approach uses faster linear
programming algorithms to solve the standard bi-partite matching in time near-
linear in the size of the (complete) bi-partite graph on $A\times B$
[VDBLL+21, CKL+22] — this approach can obtain an exact result.

Nevertheless, the most common setting for general cost is still the high-
dimensional Euclidean (or $\ell_{1}$) space (see, e.g., the experiments from
[ANWR17], or this most recent paper [ARSS23]). In this setting, one can hope
for runtime $\ll n^{2}$, as the input size is only $O(nd)$.

The best algorithm for the high-dimensional setting obtains runtime of
$O(n^{1+O(1/c^{2})})$ for $c$-approximation, for $c\geq 3.4$. This follows
from using the spanner of [HPIS13] in the following general approach. One can
take the pointset $A\cup B$ and build a spanner $H$ on it. Then the EMD
problem reduces to solving the “graphical EMD” case: EMD under the metric
defined by the shortest path distance in $H$. The latter problem is equivalent
to the problem of uncapacitated min-cost flow, or transshipment problem. This
problem in turn can be solved in time near-linear in the graph size [She17,
ASZ20, Li20]. While these algorithms are for undirected graphs (and hence
would require an undirected spanner), the most recent algorithm does solve the
min-cost flow problem in directed graph in near-linear time [CKL+22].

Thus, we obtain the following statement, which is direct corollary of our
directed spanner Theorem 1.4 combined with [CKL+22]:

######  Theorem 1.6.

For any $\epsilon>0$, given two sets of points $A,B\subset\mathbb{R}^{d}$ of
size $n$, we can solve the $EMD(A,B)$ problem within $(1+\epsilon)$
approximation in time $O(n^{2-\Omega(\epsilon^{2})}\log\Delta)$ time.

###  1.2 Our techniques

The natural place to start is to understand why [HPIS13] does not answer our
main Question 1.1, instead obtaining a subquadratic-sized spanner only for
approximation $c>3.4$. First, we note that it is enough to solve the problem
for some fixed scale $r>0$: for given dataset $P$, build a spanner $H_{r}$
where all pairs of points at distance $\leq r$ have a path of length $cr$,
while no pairwise distance contracts. For this, the authors use Locality-
Sensitive Hashing, originally designed to solve the Approximate Near Neighbor
Search (ANNS) problem in $\mathbb{R}^{d}$:

######  Definition 1.7 ([HIM12]).

Fix dimension $d$, approximation $c>1$, and scale $r>0$. A distribution ${\cal
H}$ over hash functions $h:\mathbb{R}^{d}\to U$, for some discrete set $U$, is
called $(c,p_{1},p_{2})$-Locality Sensitive Hashing (LSH) if:

  * •

for any two points $p,q\in\mathbb{R}^{d}$ with $\|p-q\|\leq r$, we have
$\Pr_{h}[h(p)=h(q)]\geq p_{1}$;

  * •

for any two points $p,q\in\mathbb{R}^{d}$ with $\|p-q\|>cr$, we have
$\Pr_{h}[h(p)=h(q)]<p_{2}$.

It is known that one can obtain $(p_{1},p_{2})$-LSH with $p_{1}\leq
p_{2}^{1/c^{2}+o(1)}$ for any $p_{2}<d^{-\omega(1)}$ [AI08]. The overall
[HPIS13] algorithm proceeds as follows. Sample $L\approx 1/p_{1}$ hash
functions $h$ from $(c/2,p_{1},p_{2})$-LSH where $p_{2}=1/n^{3}$. Each such
hash function partitions the dataset $P$ into buckets. In each bucket, we
connect all points to a fixed point with an edge of length $cr/2$ — i.e., add
a star to the graph $H_{r}$. One can immediately deduce that points at
distance $\leq r$ will be connected by 2-hop path of length $cr$, and that the
total size is $O(nL)=O(n/p_{1})=O(n^{1+12/c^{2}+o(1)})$. Furthermore, since
$p_{3}=1/n^{3}$, one can argue that no pair at distance $<cr$ ends up in the
same bucket.

Note the size is sub-quadratic only for $c>\sqrt{12}>3.4$, and there are two
contributions to the exponent 12. The first one is the “star” gadget inside
the bucket: most colliding points are connected by a 2-hop path that imposes a
factor-2 stretch. The second one is the fact that we need to set
$p_{2}=1/n^{3}$ to ensure that no pair of points at distance $>cr$ collide in
a bucket.

As we discuss below, both these sources of stretch loss are intrinsic to the
algorithm and require new ideas to overcome.

#### Lower bound.

First, we show that we cannot obtain approximation $c<2$ using vanilla
spanners or even spanners with Steiner points in the Euclidean/Hamming metric.
Indeed, consider a random pointset $P$ on the surface of a unit sphere in
$\mathbb{R}^{d}$. Then all distances are concentrated around $\sqrt{2}$. It is
immediate that, for any spanner $H_{r}$, any pair of points without a direct
edge will have stretch 2. One can also show that even if we have Steiner
points in $\mathbb{R}^{d}$, then a subquadratic-sized spanner much have
stretch at least $\sqrt{2}$. For intuition, note that the best Steiner point
for $P$ is the center of the sphere. A similar lower bound holds for Steiner
spanners in the Hamming space.

#### Upper bound.

To deal with the first source of approximation from [HPIS13] algorithm, we
consider adding Steiner vertices to the spanner that does not represent points
in the metric itself. In particular, in the above equidistant case, the
solution is to add a node $s$ to the graph, and connect it to each of the
points in $P$ with an edge of length $cr/2$. We term this a “star gadget”
below.

Now we can focus on the second source of stretch: that we need to set $p_{2}$
as low as $1/n^{3}$, which is a much more significant technical challenge. The
natural first question would be: why not set $p_{2}\approx 0.1/n$ and hence
$p_{1}=1/n^{1-\epsilon}$ for $c=1+\epsilon$?

Consider a pair of points $p,q\in P$ at distance $\leq r$ that we would like
to collide in some bucket, in which case they are connected by a path of
distance $cr$ (using our new star gadget from above). It is immediate to argue
that $p,q$ will collide with probability $p_{1}$, and hence $1-o(1)$ over all
$L$ hash functions. The tricky part is to ensure that this successful bucket
does not also contain a pair of far points (i.e., at distance $>cr$), in which
case the star gadget will shortcut the pair.

To analyze the probability of far pair of points falling into the bucket, we
can consider, for example, the probability that a “far” point $f\in P$ at
distance $\|q-f\|>cr$ collides with $q$. Standard analysis says that the
expected number of far points is $\leq p_{2}n$, and hence, by Markov’s,
there’s, say, $\Omega(1)$ probability that no far point collides with $q$. The
crucial caveat is that this probability is not independent of the event that
$p,q$ collide: i.e., it may be the case that whenever $p,q$ collide, the
number of colliding far points is much larger than the expectation.

We are lead to consider the “3-point collision” probability:
$\Pr[(h(f)=h(q))\wedge(h(q)=h(p))]$. If we were able to prove that these two
events are essentially independent, we would be all set. Such property has
indeed been considered, at least in [AR15] who used it for data-dependent LSH
algorithms. They proved such desired independence by a very intricate
reduction to the “pseudo-random” case: where $P$ is essentially random on the
sphere, except for the pair of interest $p,q$. Alas, their reduction does not
seem applicable here for a couple of reasons. The first is that the
independence holds only in the case when far point $f$ is far from both $p$
and $q$. The second is that, while in [AR15] one can think of $p$ being a
“rare” close point to $q$ (this helps in the reduction), in our setting, there
could be both $\Omega(n)$ close points and $\Omega(n)$ far points for most
$q$’s!

Our approach is different and uses two main ideas: the first enough to get
directed spanners, and the second necessary for the undirected spanners.

#### Upper bound: first idea.

We circumvent the “3-point collision” analysis by considering a different
setting of the hashing, roughly corresponding to the ANNS algorithm with sub-
polynomial query time. In particular, we use the hashing scheme from [ALRW17].
Think of the dataset as being two sets $P$ and $Q$, and we need to worry only
about the collision of points $p\in P$ vs $q\in Q$ (in the end we take $Q=P$).
Then [ALRW17] design a hashing scheme such that for some $L=n^{O(1)}$, there’s
a function $h_{P}:\mathbb{R}^{d}\to 2^{[L]}$ which describes for each point
$p\in P$ which set of buckets it is hashed to, and there’s an equivalent
$h_{Q}:\mathbb{R}^{d}\to 2^{[L]}$ function. Then we have that, for any pair
$p,q$ at distance $\leq r$, we have that $h_{P}(p)\cap h_{Q}(q)\neq\emptyset$
with constant probability. Furthermore, $|h_{P}(p)|=n^{\rho_{P}+o(1)}$ and
$|h_{Q}(q)|=n^{\rho_{Q}+o(1)}$ for $\rho_{Q},\rho_{P}\geq 0$ satisfying some
relation, and the runtime to compute $h_{P}(p),h_{Q}(q)$ is roughly
proportional to their output size. It is possible to set $\rho_{Q}=0$ in which
case $\rho_{P}\approx 1/\epsilon^{2}$ (we note that this bound is tight
[ALRW17]).

Our solution uses the above asymmetric hashing as follows: split the dataset
$P$ into $\approx n^{1-\epsilon^{2}/2}$ groups of size $m=n^{\epsilon^{2}/2}$.
For each group, preprocess as above, taking a total of $\approx n/m\cdot
m^{\rho_{P}}<n^{1.5}$ time, and then query each $q\in Q$, taking a total of
$\approx n\cdot n/m=n^{2-\epsilon^{2}/2}$ time. We can then prove that, for
every close pair $p\in P,q\in Q$, with probability at least $1/2$, there
exists a bucket where 1) $p,q$ collide, but 2) contains no point $f$ that is
far from $q$.

The remaining caveat is that we need to verify that a bucket succeeded — all
hashed $p,q$ are close to each other — as we cannot add star gadget to the
failed ones (otherwise, we create shortcuts). For this, we need to employ
furthest neighbor search data structure. A naïve adaptation of the best
currently known data structure, would result in extra runtime $\approx
n^{2-\epsilon^{3}}$, a slow-down we manage to avoid.

#### Upper bound: second idea.

The above procedure obtains only a directed spanner since we guarantee
distances between $p\in P$ and $q\in Q$ but among $p,p^{\prime}\in P$ pairs or
$q,q^{\prime}\in Q$ pairs. This turns out to be much more difficult to ensure.

In fact, our original “star gadget” is not even enough to get an undirected
spanner. In particular, consider the case when, we have $n/2$ points $P$ drawn
from sphere of radius $a=2$ and $Q$ drawn sphere of radius $b=1$. Then the
distance between a pair $p\in P,q\in Q$ is typically
$\sqrt{a^{2}+b^{2}}=\sqrt{5}$; fix $r=\sqrt{5}$. At the same time the distance
between points $p,p^{\prime}\in P$ is $\sqrt{2}a=\sqrt{8}>r$. It seems
impossible to construct an undirected spanner of sub-quadratic size with
stretch $1+\epsilon$ using the “star gadget” from before — because it would
shortcut $P$-to-$P$ distances.

Instead, we introduce a new gadget: asymmetric star gadget. In particular, in
the above example, we have a Steiner vertex $s$ that is connected with
distance $\sqrt{2}a/2$ to points $p\in P$ and with distance
$\sqrt{a^{2}+b^{2}}-\sqrt{2}a/2\geq\sqrt{2}b/2$ to points $q\in Q$. Now the
distance $P$-to-$Q$ is $r$; $P$-to-$P$ is $\sqrt{2}a$; and $Q$-to-$Q$ is
$\geq\sqrt{2}b$ as well. While the $Q$-to-$Q$ distance is stretched (it will
be taken care of at a different scale $r$), the $r$-scale distances are taken
care of, and there are not shortcuts created.

To be able to use this gadget, we start from where we left off with the
directed spanner: a pair of sets of $P^{\prime}\subset P,Q^{\prime}\subset Q$
such that each $p\in P^{\prime}$ is close to each $q\in Q^{\prime}$. We show
that in this case, there exists $a,b$ with $a+b\leq r$, such that we can
decompose $P^{\prime}$ (and $Q^{\prime}$) into smaller parts so that the
diameter of each part is $(1+\epsilon)a$ (and $(1+\epsilon)b$ respectively).
The number of such parts is bounded by $P^{\prime 1-\Theta(\epsilon)}$ and
$Q^{\prime 1-\Theta(\epsilon)}$ respectively. Then we use the asymmetric
gadget on each pair of such parts.

### Acknowledgements

We thank Negev Shekel Nosatzki for important discussions and suggestions for
the undirected spanner construction in Section 4. Research supported in part
by NSF (CCF2008733) and ONR (N00014-22-1-2713).

##  2 Lower Bound for Spanners, with or without Steiner Points

In this section, we prove the lower bounds on the size of the spanner for
geometric pointsets. We consider spanners that contains Steiner nodes
corresponding to points in the metric. We note that since the spanner cannot
shortcut any pair, for any spanner edge connecting two points
$x,y\in\mathbb{R}^{d}$, the optimal length of the edge is the distance between
points $x$ and $y$.

We prove lower bounds for both the Hamming and Euclidean ($\ell_{2}$) spaces
separately.333While it is known that $\ell_{2}$ can be embedded into
$\ell_{1}$ (and $\ell_{1}$ into $\ell_{2}$-squared), a lower bound for the
$\ell_{2}$ ($\ell_{1}$) space does not immediately imply a lower bound for the
$\ell_{1}$ (resp. $\ell_{2}$) space since the Steiner points are to be taken
in the considered space. Both lower bounds use the following lemma, which we
prove in Section 2.3.

######  Lemma 2.1.

Consider a graph $G=(V,E)$ and integer $k$. Let $P_{x},P_{y}\subseteq V$ be
any disjoint sets. Suppose $|P_{x}|=|P_{y}|=n$ and
$|V|\leq|E|=o(n^{2}/k^{2})$. For every $x\in P_{x}$ and $y\in P_{y}$, let
$S_{x,y}$ be any path from $x$ to $y$ in $G$. Then, there exists $k$ distinct
points $x_{1},\cdots,x_{k}\in P_{x}$ and $k$ distinct points
$y_{1},\cdots,y_{k}\in P_{y}$, such that there is a node that lays on all
paths $S_{x_{1},y_{1}},S_{x_{2},y_{2}},\cdots,S_{x_{k},y_{k}}$.

###  2.1 Lower bound in the Hamming metric

We prove the following lower bound on Steiner spanner size in the $\ell_{1}$
metric.

######  Theorem 2.2 (Restatement of Theorem 1.2).

For any $\epsilon\in(0,1)$, there exists a point set $P\subset\\{0,1\\}^{d}$
such that the following holds. Let $H=(P\cup S,E)$ be any spanner that can use
extra Steiner points $S\subseteq\\{0,1\\}^{d}$, but can only use the
$\ell_{1}$ distance as the edge weight between two points. Suppose for all
$u,v\in P$, the distance between $u$ and $v$ on graph $H$ satisfies

$\|u-v\|_{1}\leq\mathrm{d}_{H}(u,v)\leq(1+\epsilon)\|u-v\|_{1},$

then $H$ must use $\Omega(n^{2}(1-\epsilon)^{4})$ edges.

###### Proof of Theorem 2.2.

Let $P$ be chosen as every point is i.i.d. uniformly sampled from the hamming
cube $\\{0,1\\}^{d}$ with $d=\omega(\log^{2}n)$. With high probability, every
pair of points in $P$ has distance $\in d/2\pm o(1)d$.

For every two points $x,y\in\\{0,1\\}^{d}$, we define
$A_{x,y}:=\\{z\in\\{0,1\\}^{d}\mid\|x-z\|_{1}+\|y-z\|_{1}\leq\frac{\delta}{2}\cdot
d+\|x-y\|_{1}\\}$, where $\delta=(1+\epsilon)/2$ is taking average of $1$ and
$\epsilon$. Intuitively, for $x,y\in P$, the set $A_{x,y}$ contains all
possible Steiner points $s$ in $\\{0,1\\}^{d}$ such that the path
$x\rightarrow s\rightarrow y$ won’t have large approximation: if
$\|x-s\|_{1}+\|s-y\|_{1}\leq(1+\epsilon)\|x-y\|_{1}$, then $s\in A_{x,y}$
since $(1+\epsilon)\|x-y\|_{1}\leq\frac{\delta}{2}\cdot d+\|x-y\|_{1}$.

The following claim shows that $A_{x,y}$ has small volume.

######  Claim 2.3.

For every $p\in\\{0,1\\}^{d}$, if $x,y$ are uniformly sampled from
$\\{0,1\\}^{d}$, then

$\displaystyle\Pr_{x,y}[p\in A_{x,y}]\leq\exp(-\frac{1}{8}(1-\delta)^{2}d).$

###### Proof.

Define $S=\\{i\in[d]\mid x_{i}=y_{i}\\}$ be the set of coordinates where $x$
and $y$ agree on. $A_{x,y}$ has an equivalent definition
$A_{x,y}=\\{z\in\\{0,1\\}^{d}\mid\|z_{S}-x_{S}\|_{1}\leq\frac{\delta}{4}\cdot
d\\}$. For $i\in[d]$, let $X_{i}$ be the random variable that $X_{i}=1$ if
$i\in S$ and $p_{i}=x_{i}$, otherwise $X_{i}=0$. If $x,y$ are sampled
uniformly randomly from $\\{0,1\\}^{d}$, then each $X_{i}=1$ with
$\frac{1}{4}$ probability and $X_{i}=0$ with $\frac{3}{4}$ probability, and
all $X_{i}$ are independent. And $p\in A_{x,y}$ is equivalent to $\sum
X_{i}\leq\frac{\delta}{4}\cdot d$.

By Chernoff bound $\Pr[X\leq(1-\alpha)\operatorname*{{\mathbb{E}}}[X]]\leq
e^{-\alpha^{2}\operatorname*{{\mathbb{E}}}[X]/2}$, replacing $\alpha$ with
$1-\delta$, we have

$\displaystyle\Pr_{x,y}[p\in
A_{x,y}]=\Pr[\sum_{i}X_{i}\leq\frac{\delta}{4}\cdot
d]\leq\exp(-\frac{1}{8}(1-\delta)^{2}d).$

∎

We are now ready to proceed with the main argument. For any $P$, let $H$ be
any spanner stated in this theorem. Suppose $H$ has $o(n^{2}/k^{2})$ edges for
some $k$ tbd. By Lemma 2.1, there must exist $2k$ distinct points
$x_{1},y_{1},\cdots,x_{k},y_{k}\in P$ such that the shortest path between
$(x_{1},y_{1}),\cdots(x_{k},y_{k})$ intersect on some vertex $v\in H$ (which
could be Steiner or an original point in $P$). Since the edge weight can only
use the actual Hamming distance, we must have
$\|x_{i}-v\|_{1}+\|y_{i}-v\|_{1}\leq(1+\epsilon)\|x_{i}-y_{i}\|_{1}\leq\|x_{i}-y_{i}\|_{1}+\frac{\delta}{2}d$
for all $i$. Thus, $v$ must be in every $A_{x_{i},y_{i}}$ by definition of
$A_{x,y}$.

Define the event $E$ as follows: there exists a point $p\in\\{0,1\\}^{d}$, and
$2k$ distinct points $x_{1},y_{1},\cdots,x_{k},y_{k}\in P$ such that $p\in
A_{x_{i},y_{i}},\leavevmode\nobreak\ \forall i\in[k]$. We have argued that if
the claimed spanner with $o(n^{2}/k)$ edges exists for every $P$, then
$\Pr_{P}[E]=1$. We will show next that when $k>24(1-\delta)^{-2}$, the
probability $E$ happens (over the random choice of $P$) is less than $1$.
Hence, there exists a dataset $P^{*}$ for which $E$ does not happen, and
therefore a claimed spanner $H$ does not exist for $P^{*}$.

By Claim 2.3, for a fixed $p\in\\{0,1\\}^{d}$, we have

$\displaystyle\Pr_{x,y\sim\\{0,1\\}^{d}}[p\in
A_{x,y}]\leq\exp(-\frac{1}{8}(1-\delta)^{2}d)$

Therefore, for $k>24(1-\delta)^{-2}$,

$\displaystyle\leavevmode\nobreak\ \Pr[\exists\text{\leavevmode\nobreak\
distinct\leavevmode\nobreak\ }x_{1},y_{1},\cdots,x_{k},y_{k}\in
P,\leavevmode\nobreak\ \mathrm{such\leavevmode\nobreak\
that}\leavevmode\nobreak\ p\in\cap_{i\in[k]}A_{x_{i},y_{i}}]$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
n^{2k}\cdot(\Pr_{x,y}[p\in A_{x,y}])^{k}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \exp(2k\ln n-\frac{k}{8}(1-\delta)^{2}d)$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\ \exp(-2d).$

Thus, we conclude $\Pr[E]<2^{d}\cdot\exp(-2d)=o(1)$ by union bound on all
points $p\in\\{0,1\\}^{d}$, and therefore the theorem follows. ∎

###  2.2 Lower bound in $\ell_{2}$ metric

We now prove the lower bound for the $\ell_{2}$ metric:

######  Theorem 2.4 ($\ell_{2}$ lower bound).

For any $\epsilon\in(0,\sqrt{2}-1)$, there exists a dataset $P\subset
S^{d-1}(0,1)$, such that the following holds. Let $H=(P\cup S,E)$ be any
spanner that can use extra Steiner points $S\subset\mathbb{R}^{d}$, but can
only use the $\ell_{2}$ distance as the edge weight between two points.
Suppose for all $u,v\in P$, the distance between $u$ and $v$ on graph $H$
satisfies

$\|u-v\|_{2}\leq\mathrm{d}_{H}(u,v)\leq(\sqrt{2}-\epsilon)\|u-v\|_{2},$

then $H$ must use $\Omega(n^{2}\epsilon^{4}/\log^{2}n)$ edges, where $n=|P|$.

First, we give some definitions. For any $\epsilon\in(0,\sqrt{2}-1)$ and two
points $x,y\in\mathbb{R}^{d}$, let $A_{x,y}^{\epsilon}$ be defined as
$A_{x,y}^{\epsilon}:=\\{p\in\mathbb{R}^{d}\mid\|x-p\|_{2}+\|y-p\|_{2}\leq(\sqrt{2}-\epsilon)\|x-y\|_{2}\\}$.
If $\epsilon$ is clear from the context, we write it as $A_{x,y}$.

The following lemma shows that for a fixed point $p$, it is rare $A_{x,y}$
contains $p$ for a random pair of points $x$ and $y$.

######  Lemma 2.5.

For $\epsilon\in(0,\sqrt{2}-1)$, let $p\in B^{d}(0,1)$ be any point in the
unit ball. Let $x,y$ be sampled uniformly from unit sphere $S^{d-1}$. Then

$\Pr_{x,y\sim S^{d-1}}[p\in A_{x,y}^{\epsilon}\mid\|x-y\|_{2}\in(1\pm
o_{\epsilon}(1))\sqrt{2}]\leq e^{-\epsilon^{2}d/2}.$

###### Proof.

It is enough to bound $\Pr_{x,y\sim S^{d-1}}[p\in A_{x,y}\mid\|x-y\|_{2}=2t]$
for any fixed $t\in(1\pm o_{\epsilon}(1))\sqrt{2}/2$. By symmetry, this is
equivalent to

$\Pr_{p^{\prime}\sim S^{d-1}(0,r)}[p^{\prime}\in
A_{x,y}]=\frac{\operatorname{Vol}(A_{x,y}\cap
S^{d-1}(0,r))}{\operatorname{Vol}(S^{d-1}(0,r))},$

where $r:=\|p\|_{2}$, and $x,y$ can be any two fixed points on $S^{d-1}$ that
$\|x-y\|_{2}=2t$, say,
$x=(-t,\sqrt{1-t^{2}},0_{d-2}),y=(t,\sqrt{1-t^{2}},0_{d-2})$.

Note that $A_{x,y}$ is an ellipsoid with focal points on $x$ and $y$. Let
$c=(0,1,0_{d-2})$. Let

$\displaystyle s:=$ $\displaystyle\leavevmode\nobreak\ \min_{z\in
A_{x,y}}\langle
z,c\rangle\geq\sqrt{1-t^{2}}-\sqrt{(\sqrt{2}-\epsilon)^{2}t^{2}-t^{2}}$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\
\frac{1}{\sqrt{2}}+o_{\epsilon}(1)-\frac{\sqrt{1-2\sqrt{2}\epsilon+\epsilon^{2}}}{\sqrt{2}}-o_{\epsilon}(1)$
$\displaystyle\geq$ $\displaystyle\leavevmode\nobreak\ \epsilon.$

This means $A_{x,y}\cap S^{d-1}(0,r)\subseteq\textrm{Cap}(r,c,s)$, where
$\textrm{Cap}(r,c,s)$ is the sphere cap including all points $x\in
S^{d-1}(0,r)$ for which $x\cdot c\geq s$. Using the bound on the volume of a
high dimensional sphere cap given by [Tko12], we get

$\frac{\operatorname{Vol}(\textrm{Cap}(r,c,s))}{\operatorname{Vol}(S^{d-1}(0,r))}\leq
e^{-d(s/r)^{2}/2}=e^{-\epsilon^{2}d/2}.$

∎

###### Proof of Theorem 2.4.

Let $P$ be generated as every point is i.i.d. uniformly sampled from unit
sphere $S^{d-1}(0,1)$ with $d=\omega(\log^{2}n)$. With high probability, every
pair of points in $P$ has distance $\in\sqrt{2}\pm o(1)$.

Let $H$ be any spanner stated in this theorem with $o(n^{2}/k^{2})$ edges for
$k=10\log n/\epsilon^{2}$. Wlog, we can assume every Steiner point of $H$ is
in the unit ball $B^{d}(0,1)$, since otherwise we can project them onto the
unit sphere. By Lemma 2.1, there must exists $2k$ distinct points
$x_{1},y_{1},\cdots,x_{k},y_{k}\in P$ such that the shortest path between
$(x_{1},y_{1}),\cdots,(x_{k},y_{k})$ intersect on some point $v\in H$. Since
the edge weight can only use the actual distance in the Euclidean space, we
must have
$\|x_{i}-v\|_{2}+\|y_{i}-v\|_{2}\leq(\sqrt{2}-\epsilon)\|x_{i}-y_{i}\|_{2}$
for all $i$. Let $v^{\prime}$ be the closest point to $v$ such that every
coordinate of $v^{\prime}$ is a multiple of $\frac{\epsilon}{10\sqrt{d}}$, and
thus $\|v-v^{\prime}\|_{2}\leq\epsilon/10$, and therefore, $v^{\prime}$
satisfies that for all $i$,

$\|x_{i}-v^{\prime}\|_{2}+\|y_{i}-v^{\prime}\|_{2}\leq(\sqrt{2}-\epsilon/2)\|x_{i}-y_{i}\|_{2}.$

Let $N$ include all points in ball $B^{d}(0,r)$ whose coordinates are multiple
of $\frac{\epsilon}{10\sqrt{d}}$ and let the event $E$ be: there exists a
point $p\in N$ and $2k$ distinct points $x_{1},y_{1},\cdots x_{k},y_{k}\in P$
such that for all $i\in[k]$ $p\in A^{\epsilon/2}_{x_{i},y_{i}}$. The above
argument indicates that if such a spanner exists, then $E$ must happen. Next,
we will show that $E$ happens with probability $<1$ for a random dataset $P$;
therefore, we assert that such spanner $H$ does not exist for some $P$.

Let $p\in N$ be any point. Since every pair of points in $P$ has distance
$\in\sqrt{2}\pm o(1)$, by Lemma 2.5, we have

$\displaystyle\leavevmode\nobreak\ \Pr[\exists x_{1},y_{1},\cdots
x_{k},y_{k},\leavevmode\nobreak\ \leavevmode\nobreak\
\text{s.t.}\leavevmode\nobreak\ \leavevmode\nobreak\
p\in\cap_{i}A^{\epsilon/2}_{x_{i},y_{i}}]$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ n^{2k}\cdot\left(\Pr_{x,y}[p\in
A_{x,y}\mid\|x-y\|_{2}=\sqrt{2}\pm o(1)]\right)^{k}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\ \exp(2k\ln n-\epsilon^{2}dk/8)$
$\displaystyle=$ $\displaystyle\leavevmode\nobreak\ \exp(-d\log n).$

By union bound on all $p\in N$, we have

$\Pr[E]\leq\exp(-d\log n)\cdot(20\sqrt{d}/\epsilon)^{d}=o(1),$

therefore, the theorem follows. ∎

###  2.3 Proof of Lemma 2.1

###### Proof of Lemma 2.1.

Suppose there is a graph $G$ for which the property doesn’t hold. We will turn
$G$ into another bipartite graph $H=(P_{x}\cup P_{y},E^{\prime})$ with less
than $n^{2}$ edges but can connect all pairs of points $x\in P_{x}$ and $y\in
P_{y}$ by a direct edge. Thus, by proof of contradiction, we can conclude such
graph $G$ doesn’t exist.

First of all, we assume every path $S_{x,y}$ never touches $P_{x}$ or $P_{y}$
except its endpoints, since otherwise, we can create dummy points for every
point in $P_{x}$ and $P_{y}$ and let the path $S_{x,y}$ use dummy points. If
the new graph has $k$ paths intersecting on one point, then so does the
original graph.

Next, to simplify the proof, we give direction to edges. Let $S_{x,y}$ be any
path, and let $\\{v_{1},\cdots,v_{k}\\}$ be points on the path in order. We
say the directed edge $e=(a,b)\in S_{x,y}$ if $a=v_{i}$ and $b=v_{i+1}$ for
some $i$. We assume $G$ only has useful edges. From now on, $G$ is a directed
graph and

$E=\bigcup_{x\in P_{x},y\in P_{y}}\bigcup_{(a,b)\in S_{x,y}}\\{(a,b)\\}.$

To turn $G$ into $H$, we have three intermediate steps – from $G$ to $G_{1}$,
$G_{2}$, $G_{3}$, then $H$, each graph has better properties. In the first
graph $G_{1}=(V_{1},E_{1})$, we will have $|V_{1}|=O(|V|)$, $|E_{1}|=O(|E|)$,
and every vertex is light which we will explain later. The procedure of making
$G_{1}$ is as follows.

For every vertex $v\in V$, let $U(v)$ be initially empty. For every path
$S_{x,y}$ with $x\in P_{x}$ and $y\in P_{y}$, let $\\{v_{1},\cdots,v_{k}\\}$
be the points on the path. For every $i\in[k]$, we add $(x,y)$ to $U(v_{i})$.

We show that we modify the graph to obtain a simpler condition — that $U(v)$
contains $<k$ of either distinct $x$’s or distinct $y$’s. For every vertex
$v\in V\backslash(P_{x}\cup P_{y})$, $U(v)$ can be regarded as a bipartite
graph with a collection of edges between $P_{x}$ and $P_{y}$. In this
bipartite graph, the maximum matching is less than $k$, otherwise there are
$k$ paths with distinct endpoints intersecting on $v$.

######  Theorem 2.6 (Extended Hall’s theorem).

For any bipartite graph $G=(L,R,E)$ with $|L|=|R|=n$, the cardinality of
maximum matching is

$\mu(G)=n-\max_{T}(|T|-|N(T)|),$

where $T$ range over all subset of $L$ and $R$ separately, and $N(T)$ denote
the set of neighbors of the set $T$ in $G$.

Apply the above theorem on the bipartite graph $U(v)$, there must be a set
$T\subseteq P_{x}$ or $T\subseteq P_{y}$ such that $n-|T|+|N(T)|=\mu(U(v))<k$.
We must have $|T|\geq n-k$ and $|N(T)|\leq k$. The analysis for the cases
$T\subseteq P_{x}$ and $T\subseteq P_{y}$ would be similar, so we assume the
first case. Let $T_{L}=T$ and $T_{R}=P_{y}\backslash N(T)$. Note that there is
no path $S_{x,y}$ in $G$ crossing $v$ with $x\in T_{L}$ and $y\in T_{R}$. In
the new graph $G_{1}$, we create three copies of $v$: $v_{T_{L},\bar{T}_{R}}$
and $v_{\bar{T}_{L},T_{R}}$ and $v_{\bar{T}_{L},\bar{T}_{R}}$, where
$\bar{T}_{L}:=P_{x}\backslash T_{L}$ and $\bar{T}_{R}:=P_{y}\backslash T_{R}$.
So $|V_{1}|\leq 3|V|$. For each edge $(u,v)$ in $G$, we create at most $9$
edges linking each pair of copies of $u$ and $v$. Thus, $|E_{1}|\leq 9|E|$.

Let $\\{v_{1},\cdots,v_{l}\\}$ be vertices on path $S_{x,y}$. For all $2\leq
i\leq k-1$, we replace $v_{i}$ with its copy $v_{S,T}$ where $x\in S,y\in T$
and get a path $S^{\prime}_{x,y}$ in $G_{1}$. In the new graph $G_{1}$, for
every vertex $v\in V_{1}$, let $L(v),R(v)$ be initially empty. For every path
$S^{\prime}_{x,y}$ with $x\in P_{x}$ and $y\in P_{y}$, let
$\\{v_{1},\cdots,v_{l}\\}$ be the points on the path. For every $i\in[l]$, we
add $x$ to $L(v_{i})$ and add $y$ to $R(v_{i})$.

Since $|\bar{T}_{L}|,|\bar{T}_{R}|\leq k$ from the construction of $G_{1}$,
for every vertex $v\in V_{1}\backslash(P_{x}\cup P_{y})$, we have either
$|L(v)|\leq k$ or $|R(v)|\leq k$. If $|L(v)|\leq k$, we call $v$ left-light,
otherwise we call $v$ right-light. So there are four types of points in
$G_{1}$: $P_{x}$, $P_{y}$, left-light and right-light points.

For any graph $G=(V,E)$ and a vertex $v\in V$, we call $\textrm{in}_{G}(v)$ as
the set of edges entering $v$, and $\textrm{out}_{G}(v)$ as the set of edges
leaving $v$. In some context, we also refer $\textrm{in}_{G}(v)$
$\textrm{out}_{G}(v)$ as those vertices connected with an edge
entering/leaving $v$.

Then we construct the next graph $G_{2}=(V_{2},E_{2})$ as follows. Initially,
$E_{2}=E_{1}$. Then, for every left-light vertex $v$, we delete all edges in
$\textrm{in}_{G_{1}}(v)$ and add edge $(a,v)$ for every $a\in L(v)$. For every
right-light vertex $v$, we delete all edges in $\textrm{out}_{G_{1}}(v)$ and
add edge $(v,b)$ for every $b\in R(v)$. Intuitively, the construction is
replacing edges with shortcuts. One can check that every pair of points $x\in
P_{x},y\in P_{y}$ is still connected with a path in $G_{2}$. The number of
edges is bounded by $|E_{2}|\leq|E_{1}|+|V_{1}|\cdot k$. The purpose of
constructing $G_{2}$ is to have $\textrm{in}_{G_{2}}(v)\subseteq P_{x}$ for
left-light vertices $v$, and $\textrm{out}_{G_{2}}(v)\subseteq P_{y}$ for
right-light vertices $v$. Thus, $G_{2}$ is in fact a four-layered graph
ordered from $P_{x}$ – left-light vertices– right-light vertices – $P_{y}$,
and every edge must go strictly from lower level to higher level.

To construct $H$ from $G_{2}$, we need to remove all points in
$V_{2}\backslash(P_{x}\cup P_{y})$. Define the removing procedure applied on
vertex $v$ on graph $G^{*}$, $\textsc{Remove}_{G^{*}}(v)$ as follows: delete
all edges connecting $v$, and then for every vertex
$a\in\textrm{in}_{G^{*}}(v)$ and $b\in\textrm{out}_{G^{*}}(v)$, add an edge
from $a$ to $b$.

We apply $\textsc{Remove}_{G_{2}}(v)$ on every left-light vertices $v$ in
$G_{2}$ to get graph $G_{3}=(V_{3},E_{3})$, then apply
$\textsc{Remove}_{G_{3}}(v)$ on every right-light vertices $v$ in $G_{3}$ to
get graph $G_{4}=(P_{x}\cup P_{y},E_{4})$. The order of deleting $v$ does not
affect the outcome since there are no edges connecting two left-light
vertices, nor two right-light vertices. We have

$\displaystyle|E_{3}|\leq|E_{2}|+\sum_{v\leavevmode\nobreak\
is\leavevmode\nobreak\ \textit{left-
light}}k\cdot\textrm{out}_{G_{2}}(v)\leq|E_{2}|+k|E_{1}|,$

where the last step follows by
$\textrm{out}_{G_{2}}(v)=\textrm{out}_{G_{1}}(v)$ for left-light vertices $v$.

Furthermore, we have

$|E_{4}|\leq|E_{3}|+\sum_{v\leavevmode\nobreak\ is\leavevmode\nobreak\
\textit{right-light}}k\cdot\textrm{in}_{G_{3}}(v)\leq(k+1)|E_{3}|.$

Thus,
$|E_{4}|\leq(k+1)|E_{3}|\leq(k+1)k(|V_{1}|+|E_{1}|)=O(k^{2})\cdot|E|<n^{2}$.
And $G_{4}$ is our $H$ – a bipartite graph that connects all pairs of points
from $x\in P_{x}$ and $y\in P_{y}$ with less than $n^{2}$ edges. ∎

##  3 Directed Non-metric Steiner Spanners

In this section we construct a directed non-metric Steiner spanner, proving
Theorem 1.4.

######  Theorem 3.1 (Restatement of Theorem 1.4).

Fix $\epsilon\in(0,1)$. For any dataset $P,Q\in\mathbb{R}^{d}$, there exists a
directed graph $H$ on vertices $P\cup S$, such that for every $p,q\in P$,

$\|p-q\|_{2}\leq\vec{\mathrm{d}}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

Furthermore, the number of edges of $H$, the size of $S$, and the construction
time are all bounded by $O(n^{2-\Omega(\epsilon^{2})}\log\Delta)$, where
$\Delta$ is the aspect ratio of $P$.

We prove this theorem by reducing to the one-scale case: we fix distance $r$,
and we construct a spanner $H_{r}$ such that, for all pairs of points within
distance $[r,(1+\epsilon)r]$, they are all connected in $H_{r}$ with a proper
path. Here is the formal statement.

######  Lemma 3.2.

Let $P\subset\mathbb{R}^{d}$ be a point set on the unit sphere. Let $n=|P|$,
$r=(\log n)^{-1/8}$, and $\epsilon$ is the approximation. There is an
algorithm running in $n^{2-\Omega(\epsilon^{2})}$ time, that can generate a
directed graph $H=(P\cup S,E)$ with $|E|\leq n^{2-\Omega(\epsilon^{2})}$. Here
$S$ is the set of extra non-metric Steiner points. With high probability, $H$
satisfies:

  1. (1)

$\forall p,q\in P$, $\vec{\mathrm{d}}_{H}(p,q)\geq\|p-q\|_{2}$;

  2. (2)

$\forall p,q\in P$ with $\|p-q\|_{2}\leq r$, there is a 2-hop directed path in
$H$ from $p$ to $q$ of length $\leq(1+\epsilon)r$.

The proof of this lemma is in the rest of this section. For now, we finish the
proof of our main theorem using Lemma 3.2.

###### Proof of Theorem 3.1.

In Lemma 3.2, we show how to build a spanner, so that every pair of points
$p,q\in P$ with $\|p-q\|_{2}\in[r,(1+\epsilon)r]$ are handled, given any
parameter $r$. We can do doubling on $r$ from least distance to largest
distance to create a sequence of spanners $H_{1},\cdots,H_{\log\Delta}$. Then
$H=\cup H_{i}$ is the final spanner.

There is only one issue to solve in applying Lemma 3.2: that we need $P$ to be
on the sphere and $r$ has to be about $1/\log^{1/8}n$. Indeed, it is possible
to reduce any Euclidean instance to such an instance, while preserving the
distances at the scale $r$. See one such reduction in Corollary A.2 from
[AIMN23] (based on [BRS11, Lemma 6]).

∎

###  3.1 Algorithm for one scale

The algorithm heavily uses the data-independent (asymmetric) locality
sensitive hashing from [ALRW17] as a subroutine. We use the following
primitive from [ALRW17]; while this lemma is not explicitly given in [ALRW17],
we show how it is obtained in Appendix A.

######  Lemma 3.3 (Data-independent LSH from Section 3 of [ALRW17]).

Let $r=(\log n)^{-1/8}$ be a fixed parameter, $c=1+\epsilon$ be the
approximation ratio. There is a data structure that, takes a random seed $s$,
implicitly 444$T$ can be super-polynomially large. gives two random
collections of subspaces $A_{1},A_{2},\cdots,A_{T}\subset\mathbb{R}^{d}$ and
$B_{1},B_{2},\cdots,B_{T}\subset\mathbb{R}^{d}$. For any point $p$, denote
$\mathcal{A}_{p}=\\{A_{i}:p\in A_{i}\\}$ as the set of subspaces $A_{i}$ that
contains $p$. Similarly, define $\mathcal{B}_{p}=\\{B_{i}:p\in B_{i}\\}$.
Then, for any $n=\omega(1)$, we have

  1. 1.

$\forall p\in S^{d-1}$,
$\operatorname*{{\mathbb{E}}}_{s}[|\mathcal{A}_{p}|]\leq
n^{1/\epsilon^{2}+O(1/\epsilon)}$;

  2. 2.

$\forall p\in S^{d-1}$,
$\operatorname*{{\mathbb{E}}}_{s}[|\mathcal{B}_{p}|]=n^{o(1)}$;

  3. 3.

$\forall p,q\in S^{d-1}$ that $\|p-q\|_{2}\leq r$, $\forall i\in[T]$,

$\Pr_{s}[p\in A_{i}\mid q\in B_{i}]\geq n^{-o(1)};$

  4. 4.

$\forall p,q\in S^{d-1}$ that $\|p-q\|_{2}\geq c\cdot r$, $\forall i\in[T]$,

$\Pr_{s}[p\in A_{i}\mid q\in B_{i}]\leq\frac{1}{n};$

  5. 5.

$\forall p\in S^{d-1}$, one can find all $A_{i}\in\mathcal{A}_{p}$ in
$O(|\mathcal{A}_{p}|\cdot n^{o(1)}$ time, and all $B_{i}\in\mathcal{B}_{p}$ in
$O(|\mathcal{B}_{p}|\cdot n^{o(1)})$ time.

Description of algorithm for directed spanner construction. The formal
algorithm is presented as Algorithm 1. The algorithm takes as input a dataset
$P\subseteq S^{d-1}$, a distance parameter $r\in R$, and a approximation
factor $\epsilon$, and output a Steiner spanner graph $H$. It never create
“shortcut”, i.e., $\vec{\mathrm{d}}_{H}(p,q)$ cannot be smaller than
$\|p-q\|_{2}$. For those $\|p-q\|_{2}\in[r,(1+\epsilon)r]$, it guarantees that
$\vec{\mathrm{d}}_{H}(p,q)\leq(1+\epsilon)\|p-q\|_{2}$.

The algorithm consists of $n^{o(1)}$ rounds. In each round, for every pair of
points $p,q$ at distance $\leq r$, they have $n^{-o(1)}$ chance being
connected by a 2-hop path of total length of $(1+\epsilon)r$. Furthermore, we
avoid creating a short-cut on any pair of points. Thus, after $n^{o(1)}$
rounds, we expect our guarantee is satisfied.

In each round, we first arbitrarily partition all points into groups of size
$m=n^{\epsilon^{2}/4}$. Denote groups as $P_{1},\cdots,P_{n/m}$. Then, we use
Locality Sensitive Hashing from Lemma 3.3 (with parameters $c_{1}\leftarrow
1+\epsilon$ be the approximation and $n\leftarrow Km$ for some
$K=|P|^{o(1)}$). Note that we use the same LSH function for all groups. Assume
$\\{A_{i},B_{i}\\}_{i\in[T]}$ are half-spaces generated by LSH function.
Define sets $Q_{j}\leftarrow P\cap B_{j}$ and $P_{i,j}\leftarrow P_{i}\cap
B_{j}$. Intuitively, every point in $Q_{j}$ will be close to every point in
$P_{i,j}$ for all $i$, because it’s exactly the building and querying
procedure of a nearest neighbor data structure – in the pre-processing phase,
$p\in P_{i,j}$ falls into $j$-th bucket, and in the query phase, $q\in Q_{j}$
queries the $j$-th bucket.

To guarantee that some $q\in Q_{j}$ is at distance $\leq(1+\epsilon)r$ from
all the points in $P_{i,j}$ (which may fail to happen with non-trivial
probability), we perform a Furthest Neighbor Search (FNS) check. For the
latter, we use an FNS data structure, stated in the lemma below. It follows
immediately from the reduction from [Ind01] to a nearest neighbor search data
structure, which we instantiate with the data structure from [ALRW17].

######  Lemma 3.4 (FNS data structure [Ind01, ALRW17]).

There is a $c$-approximate Furthest Neighbor Search data structure with
$O(n^{1+\rho_{P}+o(1)})$ preprocessing time and $O(n^{\rho_{Q}+o(1)})$ query
time, for any $\rho_{Q},\rho_{P}>0$ satisfying the trade-off of:

$c^{2}\sqrt{\rho_{Q}}+(c^{2}-1)\sqrt{\rho_{P}}=\sqrt{2c^{2}-1}.$

We build an FNS data structure (Lemma 3.4) for each $P_{i,j}$ with
approximation $c_{2}\leftarrow 1+\epsilon$ and parameters $\rho_{P}\leftarrow
2/\epsilon^{2}$ and $\rho_{Q}\leftarrow 0$. For every point $q\in Q_{j}$, we
check if every point in $P_{i,j}$ is $c_{2}$ approximately
$(1+\epsilon)r$-close to $q$. If so, we can safely put $q$ into $V_{i,j}$. As
a result, every point $q\in V_{i,j}$ and every point $p\in P_{i,j}$ has
Euclidean distance $\leq(1+3\epsilon)r$ so we can create an extra Steiner node
as the center and add a star gadget. We will prove later that if $p,q$ are
close, they will fall into $P_{i,j}$ and $V_{i,j}$ with $n^{-o(1)}$
probability, for some $i,j$.

Algorithm 1

1:function Build Spanner($P\subseteq S^{d-1}$, $r,\epsilon>0$)

2: Let $n=|P|$ and $m=n^{\epsilon^{2}/4}$

3: Initialize the spanner $H=(P,\emptyset)$ as a graph with vertex set $P$ but
no edges

4: for $\textrm{it}=1,2,\cdots,n^{o(1)}$ do $\triangleright$ Repeat $n^{o(1)}$
rounds to boost success probability

5: Arbitrarily partition $P$ into $n/m$ groups $P_{1},\cdots P_{n/m}$ each of
size $m$

6: Let $\\{A_{j},B_{j}\\}_{j\in[T]}$ be the LSH function stated in Lemma 3.3

7: $\triangleright$ Plug in parameter $c_{1}\leftarrow 1+\epsilon$ and
$n\leftarrow Km$ for some $K=|P|^{o(1)}$

8: Compute $Q_{j}\leftarrow P\cap B_{j}$, $\forall j\in[T]$

9: for $i\in[n/m]$, $j\in[T]$ do

10: Calculate $P_{i,j}\leftarrow P_{i}\cap A_{j}$

11: $V_{i,j}\leftarrow\emptyset$

12: Build FNS data structure for $P_{i,j}$ using Lemma 3.4

13: $\triangleright$ Plug in parameter $c_{2}\leftarrow 1+\epsilon$,
$\rho_{P}\leftarrow 2/\epsilon^{2}$ and $\rho_{Q}\leftarrow 0$.

14: for $q\in Q_{j}$ do

15: Query $q$ into the FNS data structure for $P_{ij}$ to get $f$, the
$c_{2}$-approximate furthest point

16: if $\|q-f\|_{2}\leq c_{1}r$ then

17: Add $q$ to $V_{i,j}$

18: end if

19: end for

20: Create a new Steiner node $s_{ij}$ in $H$

21: For all $q\in V_{i,j}$, add a directed edge $(q,s_{ij})$ with length $0$
to $H$

22: For all $p\in P_{i,j}$, add a directed edge $(s_{ij},p)$ with length
$(1+3\epsilon)r$ to $H$

23: end for

24: end for

25: return $H$

26:end function

###  3.2 One scale correctness: Proof of Lemma 3.2

We now prove Lemma 3.2. We first analyze the size of sets $P_{i,j}$ and
$Q_{j}$, and then bound the size of spanner.

######  Observation 3.5.

Let $P_{i,j}$ and $Q_{j}$ be defined in Algorithm 1. We have

  1. 1.

for all $i,j$, $P_{i,j}\subseteq P_{i}$ and $|P_{i}|=m$.

  2. 2.

$\sum_{j}|Q_{j}|=n^{1+o(1)}$;

  3. 3.

$\sum_{i,j}\operatorname*{{\mathbb{E}}}[|P_{i,j}|]=n^{5/4+O(\epsilon)}$;

  4. 4.

$\forall j,\sum_{i}|P_{i,j}|\leq n$,

  5. 5.

$i\in[n/m]$ and $m=n^{\epsilon^{2}/4}$.

###### Proof.

We need to prove (2), (3), (4).

For (2), (3), by Lemma 3.3, each $q\in P$ is mapped to $(Km)^{o(1)}=n^{o(1)}$
different $Q_{j}$, and each $p\in P_{i}$ is mapped to
$(Km)^{1/\epsilon^{2}+O(1/\epsilon)}=n^{1/4+O(\epsilon)}$ different $P_{i,j}$.
For (4), we note that for every fixed $j$, any $p\in P$ can appear in
$P_{i,j}$ for at most one value of $i$. ∎

###### Proof of Lemma 3.2.

We are going to prove the lemma in four aspects: the graph our algorithm
output satisfies both property (1) and (2), also the edge number and running
time are both upper bounded by $n^{2-\Omega(\epsilon^{2})}$. For simplicity,
we will run Algorithm 1 with $\epsilon=\frac{1}{3}\epsilon_{\mathrm{input}}$.
The lemma then follows with a substitution.

Property 1: $\forall p,q\in P$, $\vec{\mathrm{d}}_{H}(p,q)\geq\|p-q\|_{2}$.

The only situation we add edges is when creating paths between $P_{i,j}$ and
$V_{i,j}$, and all paths have length $(1+3\epsilon)r$. Because every $q$
enters $V_{i,j}$ only after it passes FNS test (Line 16), which means every
point in $P_{i,j}$ is $c_{1}c_{2}r<(1+3\epsilon)r$ close to $q$. So property
(1) is true.

Property 2: $\forall p,q\in P$ with $\|p-q\|_{2}\leq r$, there is a 2-hop
directed path in $H$ from $p$ to $q$ of length $\leq(1+\epsilon)r$.

Let $p,q\in P$ be any pair of points with $\|p-q\|_{2}\leq r$. Let’s compute
the probability of connecting $q$ to $p$ with a path in one round.

Suppose $p$ is partitioned into group $P_{i}$. We are going to calculate the
probability that $p\in P_{i,j}$ and $q\in V_{i,j}$, for some $j\in[T]$. Define
$F:=\\{f\in P_{i}\mid\|q-f\|_{2}>(1+\epsilon)r\\}$ as the set of far points of
$q$. If $F\cap A_{j}=\emptyset$, while $q$ is included in $B_{j}$, then $q$
will pass the FNS test and thus be included in $V_{i,j}$.

By Lemma 3.3 and the choice of our parameters ($c_{1}\leftarrow 1+\epsilon$
and $n\leftarrow Km$), we have for all $j\in[T]$,

$\Pr[p\in A_{j}\mid q\in B_{j}]=(Km)^{-o(1)}.$

and

$\Pr[f\in A_{j}\mid q\in B_{j}]=1/(Km).$

Since $|F|\leq|P_{i}|=m$, by union bound on all $f\in F$, we can bound the
probability that the bad event happens:

$\Pr[\exists f\in F,\text{\leavevmode\nobreak\ s.t.\leavevmode\nobreak\ }f\in
A_{j}\mid q\in B_{j}]\leq 1/K.$

Thus, by choose a proper $K=n^{o(1)}$, we have

$\Pr[q\in V_{i,j}\textrm{\leavevmode\nobreak\ and\leavevmode\nobreak\ }p\in
A_{j}\mid q\in B_{j}]\geq(Km)^{-o(1)}-1/K=(Km)^{-o(1)}(1-o(1)).$

Also, By Lemma 3.3, we have

$|\\{j\in[T]:q\in B_{j}\\}|=(Km)^{o(1)}\geq 1.$

Thus, with $\geq n^{-o(1)}$ probability, $p\in P_{i,j}$ and $q\in V_{i,j}$ for
some $i,j$, and hence the spanner will have a 2-hop path from $q$ to $p$, via
$s_{ij}$, with a path of length $(1+3\epsilon)r$. By repeating $n^{o(1)}$
rounds, $q$ connects to $p$ with high probability.

Bounding the number of edges. In one round, the total number of edges added
from $S$ to $P$ is at most $\sum_{i,j}|P_{i,j}|\leq n^{5/4+O(\epsilon)}$,
where the last step is by Observation 3.5. So the total number of edges from
$S$ to $P$ is at most $n^{5/4+O(\epsilon)}$.

On the other hand, the total number of edges from $Q=P$ to $S$ is at most

$n^{o(1)}\cdot\sum_{i,j}|V_{i,j}|\leq
n^{o(1)}\frac{n}{m}\cdot\sum_{j}|Q_{j}|=n^{2+o(1)}/m=n^{2-\Omega(\epsilon^{2})},$

where the first step is because $V_{i,j}\subseteq Q_{j}$, the second step is
by $\sum_{j}|Q_{j}|=n^{1+o(1)}$ (Observation 3.5).

Thus, $|E|\leq n^{2-\Omega(\epsilon^{2})}$.

Running time. By Lemma 3.3, we can find all $A_{j}$ that contains $p$ for all
$p\in P$ in $n\cdot(Km)^{1/\epsilon^{2}+O(1/\epsilon)}=n^{5/4+O(\epsilon)}$
time, and all $B_{j}$ that contains $q$ for all $q\in P$ in
$n\cdot(Km)^{o(1)}=n^{1+o(1)}$ time.

The major running time cost is on building and querying the FNS data structure
on every $P_{i,j}$. We use Lemma 3.4 with $\rho_{P}=2/\epsilon^{2}$ and
$\rho_{Q}=0$ (See line 13).

In the preprocessing phase, we spend time $\sum|P_{i,j}|^{\rho_{P}}$ to build
the FNS data structure for every $P_{i,j}$. The total time cost is

$\sum_{i,j}|P_{i,j}|^{\rho_{P}}\leq(\sum|P_{i,j}|)\cdot\max|P_{i,j}|^{\rho_{P}}\leq
n^{5/4+O(\epsilon)}\cdot m^{\rho_{P}}=n^{7/4+O(\epsilon)},$

where the second step is because $\sum|P_{i,j}|=n^{5/4+O(\epsilon)}$, and
$|P_{i,j}|\leq|P_{i}|=m$, the last step is by our choice of
$m=n^{\epsilon^{2}/4}$.

In the query phase, for every point $q\in P$, if $q$ is in $Q_{j}$, $q$ needs
to query FNS data structure built on $P_{i,j}$ for every $i\in[n/m]$. Since
$q$ is in at most $n^{o(1)}$ different $Q_{j}$’s, with our choice of
$\rho_{q}=0$, the query time cost on each point $q\in P$ is at most
$\sum_{i\in[n/m],j:q\in Q_{j}}|P_{i,j}|^{\rho_{Q}}=n^{1+o(1)}/m$. Thus, the
query time for all $q\in P$, and also the overall running time is

$n\cdot n^{1+o(1)}/m=n^{2-\Omega(\epsilon^{2})}.$

∎

##  4 Undirected Non-metric Steiner Spanners

In this section, we show how to turn the directed spanner from Theorem 3.1
into an undirected spanner, with some loss in its size. Here is the formal
statement:

######  Theorem 4.1 (Restatement of Theorem 1.5).

Fix $\epsilon\in(0,1)$. For any dataset $P\in\mathbb{R}^{d}$, we can construct
an undirected graph $H$ on vertices $P\cup S$, such that for any $p,q\in P$,

$\|p-q\|_{2}\leq\mathrm{d}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

Furthermore, the construction time, the number of edges of $H$ and the size of
$S$ are bounded by $O(n^{2-\Omega(\epsilon^{3})}\log\Delta)$, where $\Delta$
is the aspect ratio.

The proof of this theorem starts with the directed spanner constructed in the
previous section, modifying it further. We note that the directed edges appear
in line 20 to line 22 in Algorithm 1, where we link all $q\in V_{i,j}$ to
Steiner point $s_{ij}$ with edge length $(1+\epsilon)r$ and link $s_{ij}$ to
all $p\in P_{i,j}$ with edge length $0$. If these directed edges lose their
direction, they will potentially create shortcuts between $p,p^{\prime}\in
P_{i,j}$ or $q,q^{\prime}\in V_{i,j}$ (depending on how we would assign the
weights to these edges).

We show how to replace the above (directed) gadget with a more involved
(undirected) graph. For now, we focus on one $(V_{i,j},P_{i,j})$ pair. The
high level idea is to partition $V_{i,j}$ and $P_{i,j}$ into clusters of
bounded diameter $a$ and $b$, respectively, with $a+b=2(1+\epsilon)r$. Then,
for each pair of clusters $V_{ij}^{\prime}\subset
V_{i,j},P_{ij}^{\prime}\subset P_{ij}$, we add a Steiner node with connecting
to each $q\in V_{i,j}^{\prime}$ with edge of length $a/2$, and to
$P_{i,j}^{\prime}$ with edge length $b/2$. In this way, we connect $V_{i,j}$
and $P_{i,j}$ with path of length $a/2+b/2=(1+\epsilon)r$ without shortcuting
any pair of points. As long as the number of clusters is
$\ll|V_{ij}|,|P_{ij}|$, the number of edges is $\ll|V_{i,j}|\cdot|P_{i,j}|$.

We start with some definitions.

######  Definition 4.2 (Average square distance).

For a point set $A$, define
$\operatorname{avg}(A)=\sqrt{\operatorname*{{\mathbb{E}}}_{p,q\in
A}[\|p-q\|_{2}^{2}]}$. Define $\operatorname{avg}_{\max}(A)=\max_{S\subseteq
A}\operatorname{avg}(S)$.

######  Remark 4.3.

When $S$ only has two points $x,y$, $\operatorname*{{\mathbb{E}}}_{p,q\in
S}[\|p-q\|_{2}^{2}]\neq\|x-y\|_{2}^{2}$, since there is half probability that
$p=q=x$ or $p=q=y$. Thus, $\operatorname{avg}_{\max}^{2}(A)$ is can be smaller
than $\max_{p,q\in A}\|p-q\|_{2}^{2}$.

The average square distance has the following properties.

######  Claim 4.4.

If two sets of points $A,B$ satisfy $\max_{p\in A,q\in B}\|p-q\|_{2}\leq r$,
then $\operatorname{avg}(A)+\operatorname{avg}(B)\leq 2r$.

###### Proof.

The proof follows from non-embeddability of the $K_{n,n}$ metric into the
square of $\ell_{2}$. In particular, consider the following negative-type
inequality applied to $A,B$ (see, e.g., [Sei91] or [Sch35]): for any real
$a_{p},b_{q}$ with $\sum_{p\in A}a_{p}+\sum_{q\in B}b_{q}=0$, we must have:

$\sum_{i,j\in A}a_{i}a_{j}\|p-q\|_{2}^{2}+\sum_{i,j\in
B}b_{i}b_{j}\|p-q\|_{2}^{2}-2\sum_{i\in A,j\in B}a_{i}b_{j}\|p-q\|_{2}^{2}\leq
0.$

Now set $a_{p}=1/|A|$ and $b_{q}=-1/|B|$. The inequality from above becomes
$\operatorname{avg}^{2}(A)+\operatorname{avg}^{2}(B)\leq
2\operatorname*{{\mathbb{E}}}_{p\in A,q\in B}[\|p-q\|_{2}^{2}]\leq 2r^{2}$.
Thus, $\operatorname{avg}(A)+\operatorname{avg}(B)\leq\sqrt{2\cdot
2r^{2}}=2r$. ∎

Note that Claim 4.4 is also true for any subset of $A$ and $B$. Thus, we have
the following proposition.

######  Proposition 4.5.

If two sets of points $A,B$ satisfy $\max_{p\in A,q\in B}\|p-q\|_{2}\leq r$,
then $\operatorname{avg}_{\max}(A)+\operatorname{avg}_{\max}(B)\leq 2r$.

######  Definition 4.6 (Low diameter decomposition).

Let $A$ be a point set. We say $A_{1},\cdots,A_{T}$ is an _$r$ -diameter
decomposition_ of $A$, if they form a partition of $A$, and every $A_{i}$ has
diameter at most $r$.

######  Lemma 4.7.

Fix $r,\epsilon>0$. Suppose we have two point sets $A,B$ with $\max_{p\in
A,q\in B}\|p-q\|_{2}\leq r$. Let $x,y>0$ be any real number such that $x+y\leq
2(1+\epsilon)r$. Given $A_{1},\cdots,A_{k}$, an $x$-diameter decomposition of
$A$, and $B_{1},\cdots B_{l}$, a $y$-diameter decomposition of $B$, we can
build an undirected graph $H$ such that for $\mathrm{d}_{H}$ the shortest path
distance in $H$:

  * •

for all $p\in A$, $q\in B$, $\mathrm{d}_{H}(p,q)\leq(1+\epsilon)r$;

  * •

for all $p,q\in A\cup B$, $\mathrm{d}_{H}(p,q)\geq\|p-q\|_{2}$,

and the size of $H$ is $O(|A|\cdot l+k\cdot|B|)$. The construction time is
$O(|H|)$.

###### Proof.

Choose any $x_{0}\geq x$ and $y_{0}\geq y$ such that
$x_{0}+y_{0}=2(1+\epsilon)r$.

For every $A_{i}$ and $B_{j}$, we create a Steiner point $s_{i,j}$. For every
$p\in A_{i}$, add edge $(p,s_{i,j})$ with length $x_{0}/2$. For every $q\in
B_{j}$, add edge $(q,s_{i,j})$ with length $y_{0}/2$. Now, every
$p_{1},p_{2}\in A_{i}$ are connected with distance $x_{0}$, every
$q_{1},q_{2}\in B_{j}$ are connected by $y_{0}$, and every $p\in A_{i},q\in
B_{j}$ are connected by $(x_{0}+y_{0})/2=(1+\epsilon)r$. Because $A_{i}$ has
diameter at most $x\leq x_{0}$, $B_{j}$ has diameter at most $y\leq y_{0}$,
the constraint $\mathrm{d}_{H}(p,q)\geq\|p-q\|_{2}$ always holds throughout
this procedure.

The number of edges is at most
$\sum_{i\in[k],j\in[l]}(|A_{i}|+|B_{j}|)=|A|\cdot l+k\cdot|B|$. ∎

With the above lemma, it remains to show how to construct small low-diameter
decompositions, which we will do next.

###  4.1 Computing low diameter decomposition

We now show that we can compute efficient low-diameter decompositions to be
used in Lemma 4.7. We note that we use $x\approx\operatorname{avg}_{\max}(A)$
and $y\approx\operatorname{avg}_{\max}(B)$. Hence we need an efficient
algorithm to compute $\operatorname{avg}_{\max}(A)$-diameter decomposition for
any point set $A$. We will use the notions of _$r$ -close_ and _$r$ -far_.
Namely, if two points $p,q$ have distance $\leq r$, we say they are a _$r$
-close_ pair. If their distance is $>r$, we say they are a _$r$ -far pair_.

This section gives an important subroutine for the decomposition, presented as
Algorithm 2. The input set $P$ has the guarantee that at least $|P|^{2-t}$
pairs of points are $a$-close. The algorithm will then output disjoint
clusters $P_{1},\cdots,P_{T}\subseteq P$, in which every $P_{i}$ has diameter
$(1+\epsilon)a$, and $\cup P_{i}$ contains a significant portion of $P$. $c$
is a parameter the algorithm can chose from $(0,0.2]$.

Algorithm 2

1:function Extract Clusters($P\subseteq S^{d-1}$, $a>0$, $\epsilon>0$, $c>0$,
$t>0$)

2: $\triangleright$ Input guarantee: at least $|P|^{2-t}$ pairs of points are
$a$-close.

3: Let $n=|P|$.

4: Let $h$ be a random $(a,(1+\epsilon)a,p_{1},p_{2})$-LSH function, with
$p_{1}=n^{-c}$, $p_{2}=n^{-(1+\epsilon)c}$.

5: Partition $P$ into $1/p_{2}$ buckets using $h$.

6: $\triangleright$ See the proof of Lemma 4.8 for the reason why there are
$\leq 1/p_{2}$ buckets.

7: For each bucket $i$, let $C_{h,i}$ be the number of $a$-close pairs in this
bucket. Similarly, let $F_{h,i}$ be the number of $(1+\epsilon)a$-far pairs.

8: if $\exists i$, such that $C_{h,i}\geq\frac{p_{1}p_{2}}{4}n^{2-t}$ and
$F_{h,i}/C_{h/i}\leq 16\frac{p_{2}}{p_{1}}n^{t}$ then

9: Let $B_{i}$ be all points in bucket $i$.

10: repeat

11: randomly pick $k=n^{(\epsilon c-t)/2}/10$ points from $B_{i}$.

12: if they are pairwise $a$-close pairs then

13: form a cluster with them and delete them from $B_{i}$

14: end if

15: until formed $C_{h,i}/(10nk)$ clusters.

16: else

17: Go back to Line 4

18: end if

19: return all formed clusters

20:end function

The guarantees of the Algorithm 2 are captured by the following lemma.

######  Lemma 4.8 (cluster extraction).

Fix an $n$-point set $P\subset\mathbb{R}^{d}$. Let $\epsilon\in(0,2)$ be the
approximation parameter. Let $a>0$ be a parameter such that there are at least
$n^{2-t}$ $a$-close pairs, where $t=O(\epsilon)$.

For any parameter $c\in(0,0.2]$ with $\epsilon c>t$, Algorithm 2 outputs
disjoint clusters each with size $\Omega(n^{(\epsilon c-t)/2})$. Each cluster
has diameter $(1+\epsilon)a$, i.e., all its points are $(1+\epsilon)a$-close.
Moreover, the total number of points in all clusters is
$\Omega(n^{1-2c-\epsilon c-t})$. Algorithm 2 can be implemented to run in
$O(n^{1+c+t})$ expected time.

###### Proof.

In our algorithm, we pick a random $(a,(1+\epsilon)a,p_{1},p_{2})$-LSH
function with $p_{1}=1/n^{c}$ and $p_{2}=1/n^{(1+\epsilon)c}$. We note that an
$(a,(1+\epsilon)a,p_{1},p_{2})$-LSH function maps an $a$-close pair into the
same bucket with probability $\geq p_{1}$, and map a $(1+\epsilon)a$-far pair
into the same bucket with probability $\leq p_{2}$.

We can assume, wlog, that the number of buckets is at most $B=1/p_{2}$, since
otherwise, we can randomly group buckets into $1/p_{2}$ buckets, increasing
$p_{2}$ by at most a factor of $2$. The expected number of $(1+\epsilon)a$-far
pairs that collide is $\chi_{F}\leq p_{2}n^{2}$, and the expected number of
colliding $a$-close pairs is $\chi_{C}\geq p_{1}n^{2-t}$.

For any such LSH function $h$, we denote $F_{h}$ and $C_{h}$ as the number of
colliding far and close pairs, respectively. We use
${\mathbb{1}}\left[{A}\right]=1$ if $A$ is true, otherwise
${\mathbb{1}}\left[{A}\right]=0$.

Since $\operatorname*{{\mathbb{E}}}[C_{h}]=\chi_{C}$, we have

$\operatorname*{{\mathbb{E}}}[C_{h}\cdot{\mathbb{1}}\left[{C_{h}\geq\frac{1}{2}\chi_{C}}\right]]\geq\frac{1}{2}\chi_{C}.$

Also,

$\chi_{F}=\operatorname*{{\mathbb{E}}}[F_{h}]\geq\operatorname*{{\mathbb{E}}}[C_{h}\cdot\frac{F_{h}}{C_{h}}\cdot{\mathbb{1}}\left[{\frac{F_{h}}{C_{h}}\geq\frac{4\chi_{F}}{\chi_{C}}}\right]]\geq\operatorname*{{\mathbb{E}}}[C_{h}\cdot{\mathbb{1}}\left[{C_{h}\geq\frac{1}{2}\chi_{C}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\frac{F_{h}}{C_{h}}\geq\frac{4\chi_{F}}{\chi_{C}}}\right]]\cdot\frac{4\chi_{F}}{\chi_{C}}.$

Combining the above two inequalities, we get

$\operatorname*{{\mathbb{E}}}[C_{h}\cdot{\mathbb{1}}\left[{C_{h}\geq\frac{1}{2}\chi_{C}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}\frac{F_{h}}{C_{h}}\leq\frac{4\chi_{F}}{\chi_{C}}}\right]]\geq\frac{1}{2}\chi_{C}-\chi_{F}\cdot\frac{\chi_{C}}{4\chi_{F}}\geq\frac{1}{4}\chi_{C}.$

Since $C_{h}\leq n^{2}$, we get

$\Pr[C_{h}\geq\frac{1}{2}\chi_{C}\text{\leavevmode\nobreak\
and\leavevmode\nobreak\
}C_{h}/F_{h}\geq\frac{1}{4}\chi_{C}/\chi_{F}]\geq\frac{1}{4}\chi_{C}/n^{2}.$

Furthermore, there must exist some bucket $i$ such that: 1) the number of
close pairs colliding in bucket $i$ is $C_{h,i}\geq C_{h}/2B$, and 2) the
number $F_{h,i}$ of colliding far pairs satisfies that
$C_{h,i}/F_{h,i}\geq\frac{1}{4}C_{h}/F_{h}$.

This means, with probability $\geq\frac{1}{4}\chi_{C}/n^{2}\geq
p_{1}n^{-t}/4$, we succeed at the if-check in line 8, because we have a bucket
with $C_{h,i}\geq C_{h}/2B\geq\tfrac{p_{1}p_{2}}{4}n^{2-t}$ and
$F_{h,i}/C_{h,i}\leq 16\chi_{F}/\chi_{C}\leq 16\frac{p_{2}}{p_{1}}n^{t}$. Pick
$k=\sqrt{p_{1}n^{-t}/(160p_{2})}=\Theta(n^{(\epsilon c-t)/2})\geq 1$ points at
random from this bucket $i$, and call them $A$. Then, for set $F$ defined as
the $(1+\epsilon)a$-far pairs in $B_{i}$, we have
$\operatorname*{{\mathbb{E}}}[|A^{2}\cap F|]\leq
16\frac{p_{2}}{p_{1}}n^{t}\cdot k^{2}<1/10$. Thus, with $\geq 9/10$
probability, $k$ points are pairwise $(1+\epsilon)a$-close and they are
extracted in line 13. Note that each extraction will decrease $C_{h,i}$ by at
most $nk$, so we can extract $C_{h,i}/(10nk)$ times safely as the same
analysis holds.

Running time. We check line 8 for $O(n^{t}/p_{1})$ times in expectation. Each
time we use $O(n)$ time to implement the hashing. In each check, instead of
using $n^{2}$ time calculating exact $C_{h,i}$ and $F_{h,i}$, we can do
sampling to estimate. $O(\frac{n^{t}\log n}{p_{1}p_{2}})$ samples can $1+o(1)$
approximate $C_{h,i}$ w.h.p, and $O(\frac{\log n}{p_{2}^{2}})$ samples is
enough for $F_{h,i}$.

Total running time would be

$\displaystyle O\left(\frac{n^{t}}{p_{1}}\Big{(}n+B\big{(}\frac{n^{t}\log
n}{p_{1}p_{2}}+\frac{\log
n}{p_{2}^{2}}\big{)}\Big{)}+\frac{C_{h,i}k^{2}}{10nk}\right)=$
$\displaystyle\leavevmode\nobreak\ O(n^{1+c+t}+n^{4c+2\epsilon
c+2t+o(1)}+n^{4c+3\epsilon c+t+o(1)}+n^{1-2c})$ $\displaystyle=$
$\displaystyle\leavevmode\nobreak\ O(n^{1+c+t}).$

∎

###  4.2 Proof of Theorem 4.1

The last step is to compute small-diameter decomposition for sets
$V_{ij},P_{ij}$. In particular, we will use Algorithm 2 to compute
$(\operatorname{avg}_{\max}(A)+\epsilon\cdot\operatorname{dia}(A))$-diameter
decomposition of a set $A$, where $\operatorname{dia}(A)$ is the diameter of
$A$.

We accomplish this in the next three lemmas. Lemma 4.9 shows that most pairs
inside a set $A$ are at distance at most $\operatorname{avg}(A)$. Lemma 4.10
shows a decomposition of a set $A$ into clusters with diameter
$\leq(\operatorname{avg}_{\max}(A)+\epsilon\cdot\operatorname{dia}(A))$. Lemma
4.11 shows how to decompose specifically $V_{i,j}$ from Algorithm 1.

######  Lemma 4.9.

Given a point set $A$ and $\epsilon\in(0,1/2)$, let the average distance be
define in Def. 4.2, i.e.,
$\operatorname{avg}(A)=\sqrt{\operatorname*{{\mathbb{E}}}_{p,q\in
A}[\|p-q\|_{2}^{2}]}$. Then, there are at least $|A|^{2}\epsilon$ pairs of
$p,q\in A$ such that $\|p-q\|_{2}\leq(1+\epsilon)\operatorname{avg}(A)$.

###### Proof.

By Markov’s, $\Pr_{p,q\in
A}[\|p-q\|_{2}^{2}>(1+\epsilon)^{2}\operatorname{avg}^{2}(A)]\leq\frac{\operatorname{avg}^{2}(A)}{(1+\epsilon)^{2}\operatorname{avg}^{2}(A)}\leq
1-\epsilon$. Thus, there are $\epsilon$ fraction pairs of $p,q\in A$ that have
$\|p-q\|_{2}\leq(1+\epsilon)\operatorname{avg}(A)$. ∎

######  Lemma 4.10.

Fix $\epsilon>0$. Consider a set $A$ of size $n>\omega(1/\epsilon)$. We can
construct $A_{1},\cdots,A_{T}$, which is a
$(\operatorname{avg}_{\max}(A)+\epsilon\cdot\operatorname{dia}(A))$-diameter
decomposition of $A$ in $O(n^{1.4})$ time. Furthermore, we have $T\leq
n^{1-\Omega(\epsilon)}$.

###### Proof.

Since every $p,q\in A$ has $\|p-q\|_{2}\leq\operatorname{dia}(A)$, we can
compute a quantity $\widehat{\operatorname{avg}}(A)$ in
$\operatorname{poly}(1/\epsilon,\log n)$ time satisfying
$\operatorname{avg}(A)\leq\widehat{\operatorname{avg}}(A)\leq\operatorname{avg}(A)+\epsilon\cdot\operatorname{dia}(A)$
(simply by computing an empirical average of a number of sampled pairs).

By Lemma 4.9, there are at least $n^{2}\epsilon$ number of
$(1+\epsilon)\widehat{\operatorname{avg}}(A)$-close pairs. Let $t=o(1)$ so
that $n^{2}\epsilon=n^{2-t}$. Fix $c=0.05$. Run $\textsc{Extract
Clusters}(A,a\leftarrow(1+\epsilon)\widehat{\operatorname{avg}}(A),\epsilon,c\leftarrow
0.05,t)$. By Lemma 4.8, we extract $\Omega(n^{1-2c-\epsilon c-t})$ points from
$A$ and that takes $O(n^{1+c+t})$ time.

Denote the remaining part of $A$ as $A^{\prime}$. Now, iteratively recalculate
$\widehat{\operatorname{avg}}(A^{\prime})$ and run Extract Clusters on
$A^{\prime}$ until no points are remained. Denote $A_{1},\cdots,A_{T}$ as the
final partition of $A$. By Lemma 4.8, $T$ is at most $\log
n\cdot\frac{n}{n^{(\epsilon c-t)/2}}=n^{1-\Omega(\epsilon)}$ since each
$A_{i}$ has size lower bound. And every $A_{i}$ has diameter at most
$(1+\epsilon)(\operatorname{avg}_{\max}(A)+\epsilon\cdot\operatorname{dia}(A))\leq\operatorname{avg}_{\max}+3\operatorname{dia}(A)$.
The total running time is $O(\log n\cdot\frac{n}{n^{1-2c-\epsilon
c-t}}n^{1+c+t})=O(n^{1.4})$. Replace $\epsilon$ with $\epsilon/3$ to conclude
the lemma. ∎

######  Lemma 4.11 (Decompose $V_{i,j}$).

Suppose we are in $\textsc{Build Spanner}(P,r,\epsilon)$ (Algorithm 1) and let
$n$, $Q_{j}$, $V_{i,j}$ be defined in Algorithm 1. Using
$n^{2-\Omega(\epsilon^{2})}$ time, we can construct
$(\operatorname{avg}_{\max}(V_{i,j})+3\epsilon r)$-diameter decomposition of
$V_{i,j}$ with at most $|Q_{j}|^{1-\Omega(\epsilon)}$ clusters for every
$V_{i,j}$.

###### Proof.

The idea is to compute low-diameter decomposition for all of $Q_{j}$, and the
decomposition for $V_{i,j}$ can be calculated in a straightforward way.

Fix $Q_{j}$. For every $r_{0}\in\\{0,\epsilon r,2\epsilon r,\cdots,2r\\}$, we
iteratively run Algorithm 2 with parameters Extract Clusters($Q_{j}$,
$a\leftarrow r_{0}$, $\epsilon\leftarrow\epsilon$, $c\leftarrow 0.1$,
$t\leftarrow 0.1\epsilon$) and delete the extracted points from $Q_{j}$, until
we cannot extract anymore — specifically, until the Repeat loop (line 10)
cannot be satisfied within the bounded time Lemma 4.8 gives, which can be
checked directly. Let the extracted clusters be $A_{1}^{r_{0}},\cdots
A_{T}^{r_{0}}$ ($T\leq|Q_{j}|^{1-\Omega(\epsilon)}$) and the remaining set be
$A_{\textrm{re}}^{r_{0}}$ ($|A_{\textrm{re}}^{r_{0}}|\leq|Q_{j}|$). Note that
every $A^{r_{0}}_{i}$ has diameter $r_{0}$.

Now consider one $V_{i,j}$. Let
$\operatorname{avg}_{\max}(V_{i,j})=\max_{S\subseteq
V_{i,j}}\operatorname{avg}(S)$ be defined in Def. 4.2. Because every point in
$V_{i,j}$ is $r$-close to $P_{i,j}$, we have
$\operatorname{avg}_{\max}(V_{i,j})\leq 2r$. We claim that there exists
$r_{0}\leq\operatorname{avg}_{\max}(V_{i,j})+2\epsilon r$ such that the
partition of $V_{i,j}$ defined as $\\{A_{1}^{r_{0}}\cap
V_{i,j},\cdots,A_{T}^{r_{0}}\cap V_{i,j}\\}\cup\\{v\\}_{v\in
A^{r_{0}}_{\textrm{re}}\cap V_{i,j}}$ consists of at most
$|Q_{j}|^{1-\Omega(\epsilon)}$ clusters, and therefore, this is the
decomposition of $V_{i,j}$ we want. The only thing we need to prove is that
$|A^{r_{0}}_{\textrm{re}}\cap V_{i,j}|=|Q_{j}|^{1-\Omega(\epsilon)}$.

Let $B=A^{r_{0}}_{\textrm{re}}\cap V_{i,j}$. By Lemma 4.9, there are at least
$|B|^{2}\epsilon$ pairs of $p,q\in B$ with
$\|p-q\|_{2}\leq(1+\epsilon)\operatorname{avg}(B)$. Let
$r_{0}\geq(1+\epsilon)\operatorname{avg}(B)$ be the least multiplicity of
$\epsilon r$. So $r_{0}\leq\operatorname{avg}_{\max}(V_{i,j})+3\epsilon r$.
Since $A^{r_{0}}_{\mathrm{re}}$ as a remaining set fails on $\textsc{Extract
Clusters}(A^{r_{0}}_{\mathrm{re}},r_{0},\epsilon,c\leftarrow 0.1,t\leftarrow
0.1\epsilon)$, by Lemma 4.8, this means the number of $r_{0}$-close pairs is
at most $|A^{r_{0}}_{\mathrm{re}}|^{2-t}\leq|Q_{j}|^{2-0.1\epsilon}$. This
means $|B|^{2}\epsilon\leq|Q_{j}|^{2-0.1\epsilon}$. Therefore,
$|B|=|Q_{j}|^{1-\Omega(\epsilon)}$.

There are at most $O(1/\epsilon)$ different $r_{0}$ and we can try all to find
the correct one. Use Lemma 4.10, computing the decomposition for all $Q_{j}$
and $r_{0}$ uses at most $\frac{1}{\epsilon}\sum_{j}|Q_{j}|^{1.4}\leq n^{1.5}$
running time. Thus, decomposing all $V_{i,j}$ is done in time

$O(n^{1.5}+\frac{1}{\epsilon}\sum_{i,j}|V_{i,j}|)\leq
n^{2-\Omega(\epsilon^{2})}.$

∎

###### Proof of Theorem 4.1.

Suppose we are in $\textsc{Build Spanner}(P,r,\epsilon)$ (Algorithm 1). Let
$Q_{j}$, $V_{i,j}$, $P_{i,j}$ be as in the algorithm. Now, instead of doing
line 20 to line 22, we do the following.

First, compute an $(\operatorname{avg}_{\max}(P_{i,j})+2\epsilon\cdot
r)$-diameter decomposition of $P_{i,j}$, denoted as $A_{1},\cdots,A_{k}$, and
compute an $(\operatorname{avg}_{\max}(V_{i,j})+3\epsilon\cdot r)$-diameter
decomposition of $V_{i,j}$, denoted as $B_{1},\cdots,B_{l}$. Then, use the
gadget in Lemma 4.7 to add edges in our undirected spanner. The reason we can
use the gadget is because
$\operatorname{avg}_{\max}(V_{i,j})+\operatorname{avg}_{\max}(P_{i,j})\leq 2r$
by Proposition 4.5. Thus pairs in $V_{ij}\times P_{ij}$ are distorted by at
most $1+O(\epsilon)$.

Decomposing all $P_{i,j}$ can be done in running time proportional to

$\sum_{i,j}|P_{i,j}|^{1.4}\leq(\sum_{i,j}|P_{i,j}|)^{1.4}\leq n^{1.25\cdot
1.4}=n^{1.75}.$

Computing the decompositions of all $V_{i,j}$ can be done in
$n^{2-\Omega(\epsilon^{2})}$ time.

Size of spanner. By Lemma 4.7, every pair of $V_{i,j}$ and $P_{i,j}$ adds
$|V_{i,j}|\cdot k+l\cdot|P_{i,j}|$ edges to the spanner. We have
$k\leq|P_{i,j}|^{1-\Omega(\epsilon)}$ (Lemma 4.10) and
$l\leq|Q_{j}|^{1-\Omega(\epsilon)}$ (Lemma 4.11). Since $V_{i,j}\subseteq
Q_{j}$, the total size of our spanner is at most

$\log\Delta\cdot\left(\sum_{i,j}|Q_{j}|\cdot|P_{i,j}|^{1-\Omega(\epsilon)}+|Q_{j}|^{1-\Omega(\epsilon)}\cdot|P_{i,j}|\right).$

Here we copied the constraints for $Q_{j}$ and $P_{i,j}$ from Observation 3.5.

  1. 1.

for all $i,j$, $P_{i,j}\subseteq P_{i}$ and $|P_{i}|=m$.

  2. 2.

$\sum_{j}|Q_{j}|=n^{1+o(1)}$;

  3. 3.

$\sum_{i,j}\operatorname*{{\mathbb{E}}}[|P_{i,j}|]=n^{5/4+O(\epsilon)}$;

  4. 4.

$\forall j,\sum_{i}|P_{i,j}|\leq|P|=n$,

  5. 5.

$i\in[n/m]$ and $m=n^{\epsilon^{2}/4}$.

We bound the two terms as follows.

  1. 1.

$\displaystyle\leavevmode\nobreak\
\sum_{i,j}|Q_{j}|\cdot|P_{i,j}|^{1-\Omega(\epsilon)}$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\sum_{i,j}|Q_{j}|\cdot(\max_{i,j}|P_{i,j}|^{1-\Omega(\epsilon)})$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\frac{n}{m}\cdot\sum_{j}|Q_{j}|\cdot m^{1-\Omega(\epsilon)}$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
n^{2}/m^{\epsilon}=n^{2-\Omega(\epsilon^{3})},$

where the second step is because $i\in[n/m]$ (5) and (1), the third step is by
(2).

  2. 2.

$\displaystyle\leavevmode\nobreak\
\sum_{i,j}|Q_{j}|^{1-\Omega(\epsilon)}\cdot|P_{i,j}|$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
\sum_{i,j,|Q_{j}|\leq\sqrt{n}}|Q_{j}|^{1-\Omega(\epsilon)}\cdot|P_{i,j}|+\sum_{i,j,|Q_{j}|\geq\sqrt{n}}|Q_{j}|^{1-\Omega(\epsilon)}\cdot|P_{i,j}|$
$\displaystyle\leq$ $\displaystyle\leavevmode\nobreak\
\sqrt{n}^{1-\Omega(\epsilon)}\cdot\sum_{i,j}|P_{i,j}|+\sum_{j,\leavevmode\nobreak\
|Q_{j}|\geq\sqrt{n}}|Q_{j}|^{1-\Omega(\epsilon)}\cdot n$ $\displaystyle\leq$
$\displaystyle\leavevmode\nobreak\
n^{1.75+O(\epsilon)}+n^{2-\Omega(\epsilon)},$

where the second step is by $\sum_{j}|P_{i,j}|=n$ (4), the last step is by
(3).

Concluding, we proved that the size of our spanner is
$n^{2-\Omega(\epsilon^{3})}\log\Delta$. ∎

##  5 Removing dependence on $\Delta$

If we ignore the time cost for constructing, we can remove the dependence on
$\Delta$ in the number of edges used in the spanners. Below we show this for
the directed spanner reducing the size from
$n^{2-\Omega(\epsilon^{2})}\log\Delta$ to $n^{2-\Omega(\epsilon^{2})}$;
similar result for the undirected spanner is analogous. We use the idea from
[HPIS13].

We start by defining the $\delta$-net.

######  Definition 5.1 ($\delta$-net).

Let $(X,\rho)$ be a metric space, and let $\delta>0$. A maximal set
$Y\subseteq X$, such that for any $x,y\in Y$, $\rho(x,y)>\delta$, is called a
$\delta-$net for $(X,\rho)$.

Assume the dataset has closest distance $a$ and largest distance
$a\cdot\Delta$. Let $b=a\cdot\epsilon$. Define
$K=\log_{1+\epsilon}(\Delta/\epsilon)$ so that
$b\cdot(1+\epsilon)^{K}=a\cdot\Delta$. For every $i\in\\{0,1,\cdots,K\\}$, let
$N_{i}\subseteq P$ be a $b(1+\epsilon)^{i}$-net for $(P,\ell_{2})$. This means
every point $p$ not in $N_{i}$ must have a near neighbor in $N_{i}$ that is
$b(1+\epsilon)^{i}$ close, and we call this point the leader of $p$, denoted
as $L_{i}(p)$.

We can pick those nets so that

$P=N_{0}\supseteq N_{1}\supseteq N_{2}\supseteq\cdots\supseteq N_{K}.$

We suppose to run Lemma 3.2 on each net $N_{i}$ with parameter
$r_{i}=a(1+\epsilon)^{i}$. But note that many point in $N_{i}$ may not even
has a neighbor within distance $r_{i}$. Thus, we will do the following to
reduce the size of the spanner. For $i\in[k]$, let $V_{i}$ be the set of
points in $N_{i}$ that has at least one neighbor within distance $r_{i}$ in
$N_{i}$. Then we run Lemma 3.2 on each $V_{i}$ with parameter $r=r_{i}$ to get
$H_{i}$. We claim that $\cup_{i}H_{i}$ is a spanner with $(1+7\epsilon)$
dilation.

We prove by induction on the distance $r$ that for every pair of point with
$\|p-q\|_{2}\leq r$, $\mathrm{d}_{H}(p,q)\leq(1+7\epsilon)r$. Assume this is
true for all pairs of point with distance $<r$. Let $p,q$ be
$\|p-q\|_{2}=r\in[a(1+\epsilon)^{i-4},a(1+\epsilon)^{i-3}]$. If $p\in N_{i}$,
we let $x=p$, otherwise we let $x=L_{i}(p)\in N_{i}$ be the leader of $p$.
Similarly, we define $y=q$ if $q\in N_{i}$ or otherwise we let $y=L_{i}(q)$.
Then $\vec{d}_{H}(p,q)\leq\vec{d}_{H}(p,x)+\vec{d}_{H}(x,y)+\vec{d}_{H}(y,q)$.
Since $\|p-x\|_{2},\|q-y\|_{2}\leq b(1+\epsilon)^{i}<r$, by induction we must
have $\vec{d}_{H}(p,x),\vec{d}_{H}(q,y)\leq(1+7\epsilon)\cdot
b(1+\epsilon)^{i}\leq\epsilon(1+11\epsilon)r$. Since
$\|x-y\|_{2}\leq\|x-p\|_{2}+\|p-q\|_{2}+\|q-y\|_{2}\leq(1+3\epsilon)r\leq
r_{i}$ and $x,y\in N_{i}$, $x,y$ must be also in $V_{i}$. Thus, we have

$\vec{d}_{H_{i}}(x,y)\leq(1+\epsilon)r_{i}\leq(1+4\epsilon)r.$

Thus,
$\vec{d}_{H}(p,q)\leq\vec{d}_{H}(p,x)+\vec{d}_{H_{i}}(x,y)+\vec{d}_{H}(q,y)\leq(1+7\epsilon)\|p-q\|_{2}$.

Also, because $\forall p,q\in V_{i},\vec{d}_{H_{i}}(p,q)\geq\|p-q\|_{2}$, so
$\forall p,q\in P,\vec{d}_{H}(p,q)\geq\|p-q\|_{2}$.

Next, we will upper bound the size of $V_{i}$.

For every point $p\in P$ and $i\in[K]$, we create an imaginary point called
$(i,p)$ if $p\in N_{i}$. Denote $z(p)$ as the largest integer that $p\in
N_{z(p)}$. We build a tree on all such points as follows. We link an edge
between $(i,p)$ to $(i+1,p)$ for all $i\leq z(p)-1$, and link $(z(p),p)$ to
$(z(p)+1,q)$ where $q=L_{z(p)}(p)$ is the leader of $p$. The root of the tree
is $(K,p^{*})$, in which $N_{K}=\\{p^{*}\\}$ has only one point.

Consider any $i\in[K]$ and $p\in P$ such that $p\in V_{i}$. This means $p$ has
a point $q$ that is $a(1+\epsilon)^{i}$ close to $p$. By properties of
$\delta$-net, $p$ and $q$ cannot co-exists in net $N_{i+k}$, where
$k:=\log_{1+\epsilon}(b/a)$. This means there must be a vertex on the chain
$\\{(i,p),(i+1,p),\cdots,(i+k,p)\\}$ having two children.

The tree has $n$ leaves and it has at most $n-1$ vertices having two children,
so $\sum|V_{i}|=O(kn)$.

The size of the spanner $H$ is

$\sum_{i}|V_{i}|^{2-\Omega(\epsilon^{2})}=(n/\epsilon^{2})^{2-\Omega(\epsilon^{2})}=n^{2-\Omega(\epsilon^{2})}.$

######  Theorem 5.2 (Existence result for directed spanner).

Fix $\epsilon\in(0,1)$. For any dataset $P\in\mathbb{R}^{d}$, there exists a
directed graph $H$ on vertices $P\cup S$ with size
$n^{2-\Omega(\epsilon^{2})}$, such that for any $p,q\in P$,

$\|p-q\|_{2}\leq\vec{\mathrm{d}}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

Using the same technique, we can prove similar results for undirected graph.

######  Theorem 5.3 (Existence result for undirected spanner).

Fix $\epsilon\in(0,1)$. For any dataset $P\in\mathbb{R}^{d}$, there exists an
undirected graph $H$ on vertices $P\cup S$ with size
$n^{2-\Omega(\epsilon^{3})}$, such that for any $p,q\in P$,

$\|p-q\|_{2}\leq\mathrm{d}_{H}(p,q)<(1+\epsilon)\cdot\|p-q\|_{2}.$

## Appendix

##  Appendix A Data-independent LSH from [ALRW17]

We show here how Lemma 3.3 follows from results in [ALRW17, Section 3]. We use
the notations from [ALRW17], noting that our $\rho_{Q}/\rho_{P}$ corresponds
to $\rho_{q}/\rho_{u}$ from [ALRW17].

######  Definition A.1 (Definition of $\alpha(s)$, $\beta(s)$).

For any $0<s<2$, let $u,v$ be any two points on a unit sphere $S^{d-1}$ at
distance $s$. Define $\alpha(s):=1-s^{2}/2$ as the cosine of the angle between
$u$ and $v$, and $\beta(s):=\sqrt{1-\alpha^{2}(s)}$ as the sine of the same
angle.

######  Definition A.2 (Definition of $F(\eta)$ and $G(s,\eta,\sigma)$).

Let $u$ be any point on $S^{d-1}$. Define

$F(\eta):=\Pr_{z\sim N(0,1)^{d}}[\langle u,z\rangle\geq\eta].$

For any $0<s<2$, let $v$ be any point on $S^{d-1}$ with
$\operatorname{dis}(u,v)=s$. Define

$G(s,\eta,\sigma):=\Pr_{z\sim N(0,1)^{d}}[\langle
u,z\rangle\geq\eta\wedge\langle v,z\rangle\geq\sigma].$

Note that $F(\eta),G(s,\eta,\sigma)$ doesn’t depend on the specific choice of
$u$ and $v$ due to the symmetry of Gaussian.

######  Lemma A.3 (Lemma 3.1 of [ALRW17]).

For $\eta\rightarrow\infty$,

$F(\eta)=e^{-(1+o(1))\cdot\frac{\eta^{2}}{2}}.$

######  Lemma A.4 (Lemma 3.2 of [ALRW17]).

For every $s\in(0,2)$, if $\eta,\sigma\rightarrow\infty$ and
$\alpha(s)\cdot\eta<\sigma<\frac{1}{\alpha(s)}\cdot\eta$, one has

$G(s,\eta,\sigma)=e^{-(1+o(1))\cdot\frac{\eta^{2}+\sigma^{2}-2\alpha(s)\eta\sigma}{2\beta^{2}(s)}}.$

######  Lemma A.5 (Data-independent LSH from Section 3 of [ALRW17]).

Let $r\in(0,2)$ be a fixed parameter. For any integer $K\geq 1$ and
$\eta_{q},\eta_{u}>0$, there is a data structure that, takes a random seed
$s$, implicitly gives two random collections of subspaces
$A_{1},A_{2},\cdots,A_{T}\subset\mathbb{R}^{d}$ and
$B_{1},B_{2},\cdots,B_{T}\subset\mathbb{R}^{d}$. For any point $p$, denote
$\mathcal{A}_{p}=\\{A_{i}:p\in A_{i}\\}$ as the set of subspaces $A_{i}$ that
contains $p$. Similarly, define $\mathcal{B}_{p}=\\{B_{i}:p\in B_{i}\\}$.

  1. 1.

$\forall p\in S^{d-1}$,
$\operatorname*{{\mathbb{E}}}_{s}[|\mathcal{A}_{p}|]=\Theta(F(\eta_{u})/G(r,\eta_{u},\eta_{q}))^{K}$
;

  2. 2.

$\forall p\in S^{d-1}$,
$\operatorname*{{\mathbb{E}}}_{s}[|\mathcal{B}_{p}|]=\Theta(F(\eta_{q})/G(r,\eta_{u},\eta_{q}))^{K}$
;

  3. 3.

$\forall p,q\in S^{d-1},i\in[T]$,

$\Pr[p\in A_{i}\mid q\in
B_{i}]=(G(\|p-q\|_{2},\eta_{u},\eta_{q})/F(\eta_{q}))^{K}$

  4. 4.

$\forall p\in S^{d-1}$, one can find all $A_{i}\in\mathcal{A}_{p}$ in
$O(|\mathcal{A}_{p}|\cdot\log n\cdot 1/G(r,\eta_{u},\eta_{q}))$ time, and all
$B_{i}\in\mathcal{B}_{p}$ in $O(|\mathcal{B}_{p}|\cdot\log n\cdot
1/G(r,\eta_{u},\eta_{q}))$ time;

The following lemma shows that with properly chosen $\eta_{u}$, $\eta_{q}$ and
$K$, Lemma 3.3 can be proven from Lemma A.5.

######  Lemma A.6 (parameters).

Let $r=(\log n)^{-1/8}$ and $c=1+\epsilon$ is the approximation ratio. Then,
for any $n=\omega(1)$, there is a choice of $\eta_{u},\eta_{q}>0$ and $1\leq
K\leq O(\sqrt{\ln n})$ such that

  1. 1.

$(F(\eta_{u})/G(r,\eta_{u},\eta_{q}))^{K}=n^{1/\epsilon^{2}+O(1/\epsilon)}$;

  2. 2.

$(F(\eta_{q})/G(r,\eta_{u},\eta_{q}))^{K}=n^{o(1)}$;

  3. 3.

$(G(cr,\eta_{u},\eta_{q})/F(\eta_{q}))^{K}=1/n$.

  4. 4.

$1/G(r,\eta_{u},\eta_{q})=n^{o(1)}$.

###### Proof.

Let $\sigma,\tau$ be two parameters that $F(\eta_{u})^{K}=n^{-\sigma}$ and
$F(\eta_{q})^{K}=n^{-\tau}$. Thus, $G(r,\eta_{u},\eta_{q})$ can be written as
$n^{-\frac{\sigma+\tau-2\alpha(r)\sqrt{\tau\sigma}}{\beta^{2}(r)}}$. We set
$\sqrt{\tau}:=\frac{\beta(cr)}{\alpha(r)-\alpha(cr)}$ and
$\sqrt{\sigma}:=\alpha(r)\cdot\sqrt{\tau}$ as what [ALRW17] did in Section
3.3.3, in the case where $\rho_{q}=0$.

The proof of part 3 follows the same proof as in [ALRW17]. Here we have

$\displaystyle\ln\left(\frac{G(cr,\eta_{u},\eta_{q})}{F(\eta_{q})}\right)^{K}/\ln(n)=\left(\tau-\frac{\tau+\sigma-2\alpha(cr)\sqrt{\tau\sigma}}{\beta^{2}(cr)}\right)=-1.$

Also, part 2 is true because

$\displaystyle(F(\eta_{q})/G(r,\eta_{u},\eta_{q}))^{K}=n^{\rho_{q}+o(1)},$

where

$\displaystyle\rho_{q}=\frac{\sigma+\tau-2\alpha(r)\sqrt{\tau\sigma}}{\beta^{2}(r)}-\tau=\frac{(\sqrt{\sigma}-\alpha(r)\sqrt{\tau})^{2}}{\beta^{2}(r)}=0.$

For part 1, we have

$\displaystyle(F(\eta_{u})/G(r,\eta_{u},\eta_{q}))^{K}=n^{\rho_{u}+o(1)},$

where

$\displaystyle\rho_{u}=\frac{\sigma+\tau-2\alpha(r)\sqrt{\tau\sigma}}{\beta^{2}(r)}-\sigma=\frac{(\alpha(r)\sqrt{\sigma}-\sqrt{\tau})^{2}}{\beta^{2}(r)}=1/\epsilon^{2}+O(1/\epsilon)+O(r).$

Part 4 follows by computing $G$ directly and using the fact that $r=(\log
n)^{-1/8}$. ∎

## References

  * [ABS+20] Reyan Ahmed, Greg Bodwin, Faryad Darabi Sahneh, Keaton Hamm, Mohammad Javad Latifi Jebelli, Stephen Kobourov, and Richard Spence.  Graph spanners: A tutorial review.  Computer Science Review, 37:100253, 2020.
  * [ADD+93] Ingo Althöfer, Gautam Das, David Dobkin, Deborah Joseph, and José Soares.  On sparse spanners of weighted graphs.  Discrete & Computational Geometry, 9(1):81–100, 1993.
  * [AI08] Alexandr Andoni and Piotr Indyk.  Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions.  Communications of the ACM, 51(1):117–122, 2008.
  * [AIMN23] Alexandr Andoni, Piotr Indyk, Sepideh Mahabadi, and Shyam S. Narayanan.  Differentially private approximate near neighbor counting in high dimensions.  In NeurIPS, 2023.
  * [ALRW17] Alexandr Andoni, Thijs Laarhoven, Ilya Razenshteyn, and Erik Waingarten.  Optimal hashing-based time-space trade-offs for approximate near neighbors.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 47–66. SIAM, 2017.
  * [ANWR17] Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet.  Near-linear time approximation algorithms for optimal transport via sinkhorn iteration.  Advances in neural information processing systems, 30, 2017.
  * [AR15] Alexandr Andoni and Ilya Razenshteyn.  Optimal data-dependent hashing for approximate near neighbors.  2015\.  Full version at http://arxiv.org/abs/1501.01062.
  * [ARSS23] Pankaj K Agarwal, Sharath Raghvendra, Pouyan Shirzadian, and Rachita Sowle.  A higher precision algorithm for computing the $1$-wasserstein distance.  In The Eleventh International Conference on Learning Representations, 2023.
  * [ASZ20] Alexandr Andoni, Clifford Stein, and Peilin Zhong.  Parallel approximate undirected shortest paths via low hop emulators.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 322–335, 2020.
  * [BRS11] Yair Bartal, Ben Recht, and Leonard J. Schulman.  Dimensionality reduction: Beyond the johnson-lindenstrauss bound.  In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 868–887. SIAM, 2011.
  * [BT22] Sujoy Bhore and Csaba D Tóth.  Euclidean steiner spanners: Light and sparse.  SIAM Journal on Discrete Mathematics, 36(3):2411–2444, 2022.
  * [Che86] Paul Chew.  There is a planar graph almost as good as the complete graph.  In Proceedings of the second annual symposium on Computational geometry, pages 169–177, 1986.
  * [CHJ+22] CJ Carey, Jonathan Halcrow, Rajesh Jayaram, Vahab Mirrokni, Warren Schudy, and Peilin Zhong.  Stars: Tera-scale graph building for clustering and graph learning.  arXiv preprint arXiv:2212.02635, 2022.
  * [CKL+22] Li Chen, Rasmus Kyng, Yang P Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva.  Maximum flow and minimum-cost flow in almost-linear time.  In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 612–623. IEEE, 2022.
  * [Cla87] Ken Clarkson.  Approximation algorithms for shortest path motion planning.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 56–65, 1987.
  * [Cut13] Marco Cuturi.  Sinkhorn distances: Lightspeed computation of optimal transport.  Advances in neural information processing systems, 26, 2013.
  * [DEL+22] Laxman Dhulipala, David Eisenstat, Jakub Lacki, Vahab Mirrokni, and Jessica Shi.  Hierarchical agglomerative graph clustering in poly-logarithmic depth.  Advances in Neural Information Processing Systems, 35:22925–22940, 2022.
  * [Epp99] David Eppstein.  Spanning trees and spanners. handbook of computational geometry, j.-r. sack and j. urrutia, eds, 1999.
  * [Erd63] P. Erdös.  Extremal problems in graph theory.  Theory of Graphs and its Applications (Proc. Symp. Smolenice, 1963), pages 29–36, 1963.
  * [HIM12] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani.  Approximate nearest neighbor: Towards removing the curse of dimensionality.  Theory of Computing, 1(8):321–350, 2012.
  * [HPIS13] Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos.  Euclidean spanners in high dimensions.  In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 804–809. SIAM, 2013.
  * [Ind01] Piotr Indyk.  High-dimensional computational geometry.  Ph.D. Thesis. Department of Computer Science, Stanford University, 2001\.
  * [Kei88] J Mark Keil.  Approximating the complete euclidean graph.  In SWAT 88: 1st Scandinavian Workshop on Algorithm Theory Halmstad, Sweden, July 5–8, 1988 Proceedings 1, pages 208–213. Springer, 1988\.
  * [KG92] J Mark Keil and Carl A Gutwin.  Classes of graphs which approximate the complete euclidean graph.  Discrete & Computational Geometry, 7:13–28, 1992.
  * [KNP19] Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov.  Preconditioning for the geometric transportation problem.  In 35th International Symposium on Computational Geometry (SoCG 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019.
  * [Li20] Jason Li.  Faster parallel algorithm for approximate shortest path.  In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, pages 308–321, 2020.
  * [LS22] Hung Le and Shay Solomon.  Truly optimal euclidean spanners.  SIAM Journal on Computing, (0):FOCS19–135, 2022.
  * [NS07] Giri Narasimhan and Michiel Smid.  Geometric spanner networks.  Cambridge University Press, 2007.
  * [PS89] David Peleg and Alejandro A Schäffer.  Graph spanners.  Journal of graph theory, 13(1):99–116, 1989.
  * [Sch35] Isaac J Schoenberg.  Remarks to Maurice Frechet’s article “sur la definition axiomatique d’une classe d’espace distances vectoriellement applicable sur l’espace de hilbert”.  Annals of Mathematics, pages 724–732, 1935.
  * [Sei91] JJ Seidel.  Quasiregular two-distance sets.  In Geometry and Combinatorics, pages 267–273. Elsevier, 1991.
  * [She17] Jonah Sherman.  Generalized preconditioning and undirected minimum-cost flow.  In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 772–780. SIAM, 2017.
  * [Tko12] Tomasz Tkocz.  An upper bound for spherical caps.  The American Mathematical Monthly, 119(7):606–607, 2012.
  * [Vai89] Pravin M. Vaidya.  Geometry helps in matching.  SIAM Journal on Computing, 18(6):1201–1225, 1989.
  * [VDBLL+21] Jan Van Den Brand, Yin Tat Lee, Yang P Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang.  Minimum cost flows, mdps, and $\ell_{1}$-regression in nearly linear time for dense instances.  In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 859–869, 2021.
  * [Zwi01] Uri Zwick.  Exact and approximate distances in graphs—a survey.  In Algorithms—ESA 2001: 9th Annual European Symposium Århus, Denmark, August 28–31, 2001 Proceedings, pages 33–48. Springer, 2001\.