On the Difference Between Closest, Furthest, and Orthogonal Pairs:
Nearly-Linear vs Barely-Subquadratic Complexity in Computational Geometry

arXiv:1709.05282v1 [cs.CG] 15 Sep 2017

Ryan Williams∗

Abstract
Point location problems for n points in d-dimensional Euclidean space (and ℓ p spaces more generally)
have typically had two kinds of running-time solutions:
(Nearly-Linear) less than d poly(d) · n logO(d) n time, or

(Barely-Subquadratic) f (d) · n2−1/Θ(d) time, for various functions f .

For small d and large n, “nearly-linear” running times are generally feasible, while the “barelysubquadratic” times are generally infeasible, requiring essentially quadratic time. For example, in the Euclidean metric, finding a Closest Pair among n points in Rd is nearly-linear, solvable in 2O(d) · n logO(1) n
time, while the known algorithms for finding a Furthest Pair (the diameter of the point set) are only
barely-subquadratic, requiring Ω(n2−1/Θ(d)) time. Why do these proximity problems have such different time complexities? Is there a barrier to obtaining nearly-linear algorithms for problems which are
currently only barely-subquadratic?
We give a novel exact and deterministic self-reduction for the Orthogonal Vectors problem on n
vectors in {0, 1}d to n vectors in Zω (log d) that runs in 2o(d) time. As a consequence, barely-subquadratic
problems such as Euclidean diameter, Euclidean bichromatic closest pair, ray shooting, and incidence
detection do not have O(n2−ε ) time algorithms (in Turing models of computation) for dimensionality
d = ω (log log n)2 , unless the popular Orthogonal Vectors Conjecture and the Strong Exponential Time
Hypothesis are false. That is, while the poly-log-log-dimensional case of Closest Pair is solvable in
n1+o(1) time, the poly-log-log-dimensional case of Furthest Pair can encode difficult large-dimensional
problems conjectured to require n2−o(1) time.
We also show that the All-Nearest Neighbors problem in ω (log n) dimensions requires n2−o(1) time
to solve, assuming either of the above conjectures.

∗ MIT

CSAIL & EECS, rrw@mit.edu. Supported by an NSF CAREER award.

1 Introduction
Point proximity and location problems have been core to computer science and computational geometry
since Minsky and Papert [MP69] and Knuth’s post office problem [Knu73]. In this paper, we study the
problems of finding the closest pair or furthest pair in a point set (i.e., the diameter) in moderate dimensions
under the most natural norms, and incidence problems such as Hopcroft’s problem [Mat93, Eri95, Eri96]:
given n points in Rd and n hyperplanes through the origin, does any point lie on any line? (Note this is
equivalent to asking whether there are two vectors which are orthogonal, i.e., have inner product 0.) For
closest and furthest pair problems, we also consider their bichromatic versions where there are n red points,
n blue points, and we wish to find a closest (or furthest) red/blue pair. 1 We consider these problems under
the ℓ p metric for p ∈ {1, 2}, as well as ℓ∞ . As is standard, we use ℓdp to denote the metric space (Rd , ℓ p ),
with the distance functions ||x − y|| p = (∑di=1 |xi − yi | p )1/p and ||x − y||∞ = maxi |xi − yi |.
For the case of very large n and modest d, some of these problems appear to be far more difficult to solve
than others, for reasons which are still not well-understood (beyond the fact that known techniques do not
work). As early as 1976, Bentley and Shamos [BS76] noticed an apparent difference in the difficulties of
solving furthest pair and closest pair in ℓ2 in higher dimensions, and raised it as an important issue to study.
The following table gives a rough classification of key problems which are known to be “easy” and which
seem to be “hard” for large n and modest d.2
Nearly-Linear (d poly(d) · n logO(d) n time)
(Bichrom.) ℓd∞ -Furthest Pair [Yao82, GBT84]
ℓd2 -Closest Pair [BS76, KM95, DHKP97]
ℓd1 -Furthest Pair [Yao82, GBT84]
(Bichrom.) ℓd1 and ℓd∞ -Closest Pair
[GBT84, PS85, DHKP97, Cha17]

Barely-Subquadratic ( f (d) · n2−1/Θ(d) time)
ℓd2 -Furthest Pair [Yao82, AESW91]
Bichrom. ℓd2 -Closest Pair [AESW91]
d-dim. Hopcroft’s Problem [Cha93, Mat93]

Note that there are many other core geometry problems with one of the two above runtime types; the
above are just some of the core bottlenecks. For example, Hopcroft’s problem is a special case of problems
such as (batch) point location and ray shooting, which also suffer from the same n2−1/Θ(d) dependency (see
Erickson’s work on hardness from Hopcroft’s problem [Eri95] for more).
Why do some problems fall on the right side of the table, and can they be moved to the left side?
Besides the natural question of understanding the difference between furthest and closest pair, here is another
motivating example. In 1984, Gabow, Bentley, and Tarjan [GBT84] showed that the ℓ∞ -furthest pair problem
(and its bichromatic version) in Rd is very easy, solvable in Õ(d · n) time. Using this fast algorithm, along
d
with an isometric embedding of ℓd1 into ℓ2∞ , they then solve the (bichromatic or not) furthest pair problem for
ℓ1 in Õ(2d · n) time. So computing the ℓ∞ -diameter and ℓ1 -diameter are both “nearly-linear” time problems
in low dimensions.
Can similar bounds be achieved for ℓ2 -furthest pair? As the above table indicates, the best known algorithms for furthest pair in ℓ2 (bichromatic or not) still have running time bounds of the form O(n2−1/Θ(d) ),
which is “barely subquadratic.” Is there a fundamental reason why this problem is so much harder in ℓ2 than
in ℓ1 or in ℓ∞ ?
1 Note

we do not consider ℓ1 and ℓ2 bichromatic furthest pair explicitly, since it is easy to efficiently reduce between the
bichromatic version and the uncolored version. For example, we can reduce from bichromatic to non-bichromatic by adding
one extra dimension with large (positive if red, negative if blue) coordinates.
2 In this paper, we assume a machine model that allows basic arithmetic on entries of vectors and comparisons of points in Zd in
poly(d, log M) time, where M is the largest magnitude of an integer in an input. Such a concrete model is necessary for our hardness
results, which are concerned with discrete tasks such as SAT-solving in typical Turing models of computation.

1

The situation is arguably counter-intuitive, because ℓ1 and ℓ∞ are technically more “universal” metrics
than ℓ2 , so one might think that problems should be more difficult under the former than the latter. For instance, efficient isometric embeddings of n-point sets from ℓ2 into ℓ1 and into ℓ∞ are known in the literature
on metric embeddings (see the book [DL97] for references), whereas the converse is not true (see for example [WW75, Chapter 2]). However, these isometric embeddings need Ω(n) dimensions in the most general
cases. There may still be embeddings (perhaps randomized) which map low-dimensional n-point sets in ℓ2
into sub-exponential-dimensional ℓ1 (or ℓ∞ ). Indeed, in the case of low distortion (where the distances in an
embedding are allowed to shrink or grow by small multiplicative amounts) these are well-known, even deterministically in some regimes [LLR94, Ind07, GLR10]. The results of this paper show that “nice” isometric
embeddings of ℓ2 into ℓ1 would have major implications in fine-grained complexity.

1.1 Strong Difficulty of Proximity Problems in the Euclidean metric
We offer good reasons why furthest pair in ℓ2 and other barely-subquadratic problems will be difficult to
solve as fast as closest pair, even in very low dimensions. We do this by relating ℓ2 -furthest pair and other
“barely subquadratic” problems to the Orthogonal Vectors Conjecture [Wil05, AVW14] and the Strong
Exponential Time Hypothesis [IP01, CIP09] in a novel way.
The OV problem is: given n vectors v1 , . . . , vn ∈ {0, 1}d , are there i, j such that hvi , v j i = 0? Clearly
O(n2 d) time suffices for solving OV, and slightly subquadratic-time algorithms are known in the case of
small d [AWY15, CW16]. It is conjectured that there is no OV algorithm running in (say) n1.99 time for
dimensionality d = ω (log n).
Conjecture 1.1 (Orthogonal Vectors Conjecture (OVC) [Wil05, AVW14]). For every ε > 0, there is a c ≥ 1
such that OV cannot be solved in n2−ε time on instances with d = c log n.
In other words, OVC states that OV requires n2−o(1) time on instances of dimension ω (log n). OVC is
plausible because it is implied by (and looks much more likely than) the popular Strong Exponential Time
Hypothesis [IP01, CIP09] on the time complexity of solving k-SAT [Wil05, WY14].
Straightforward transformations show that OVC implies that both furthest and bichromatic closest pair
ω (log n)
ω (log n)
in ℓ1
and ℓ2
require n2−o(1) time [Wil05, AW15]. Also assuming OVC, David, Kartik, and
ω (log n)
ω (log n)
Laekhanukit [DSL16] show that (non-bichromatic) closest pair in ℓ p
for p > 2 and ℓ∞
also require n2−o(1) time. It is not so surprising that some proximity search problems in super-log dimensions are
hard under OVC, because OVC is a hardness conjecture about a problem in super-log dimensions.
In this paper, we show that OVC implies bichromatic closest pair and furthest pair in ℓ2 require essentially quadratic time for even poly-loglog dimensions, in stark contrast with bichromatic closest pair and
furthest pair in both ℓ1 and ℓ∞ (which both have n1+o(1) -time solutions in this case). Our main technical tool
is the following dimensionality reduction for Orthogonal Vectors:
Lemma 1.1 (Dimensionality Reduction for OV). Let ℓ ∈ [1, d]. There is an n · d O(d/ℓ) -time reduction from
OV for n points in {0, 1}d to d O(d/ℓ) instances of OV for n points in Zℓ+1 , with vectors of O((d log d)/ℓ)-bit
entries.
Applying this lemma, we establish quadratic-time hardness for the barely-subquadratic Hopcroft’s problem, ℓ2 -Furthest Pair, and Bichromatic ℓ2 -Closest Pair in small (poly-log-log) dimensions. It follows that if
any one of these three problems became “nearly-linear”, then there would have many interesting algorithmic
consequences, including new SAT-solving algorithms. For example:

2

Theorem 1.1 (Hardness of Hopcroft’s Problem). Under SETH (or OVC), Hopcroft’s problem in ω (log log n)
dimensions requires n2−o(1) time, with vectors of O(log n)-bit entries.
Theorem 1.2 (Hardness of ℓ2 -Furthest Pair). Under SETH (or OVC), finding a furthest pair in ω (log log n)2
dimensions under the ℓ2 norm requires n2−o(1) time, with vectors of O(log n)-bit entries.
Therefore, computing the diameter of an n-point set in low-dimensional ℓ2 is surprisingly more difficult
to solve than in the ℓ1 metric, or in the ℓ∞ metric. By Gabow-Bentley-Tarjan [GBT84], there are n2−ε -time
algorithms for furthest pair under ℓ1 up to ε log n dimensions, and under ℓ∞ up to n1−ε dimensions. There
seems to be an exponential curse of dimensionality in computing the diameter of a point set, going from ℓ∞ to
ℓ1 , and also going from ℓ1 to ℓ2 . The following table summarizes the consequences for barely-subquadratic
problems.
Barely-Subquadratic Problem
ℓd2 -Furthest Pair [Yao82, AESW91]
Bichrom. ℓd2 -Closest Pair [AESW91]
d-dim. Hopcroft’s Problem [Cha93, Mat93]

Lower Bound (Under SETH or OVC)
n2−o(1) time for d = ω (log log n)2
n2−o(1) time for d = ω (log log n)2
n2−o(1) time for d = ω (log log n)

Under the present landscape of fine-grained complexity conjectures, it follows that none of the barelysubquadratic problems we have identified can be made nearly-linear:
Corollary 1.1. Under SETH (or OVC),
none of ℓ2 -Furthest Pair, Bichromatic ℓ2 -Closest Pair, or Hopcroft’s
√
2o( d)
2−
ε
problem are solvable in n
· log
n time, for all ε > 0.
Since the above barely-subquadratic problems have closely-related nearly-linear problems, these results
also show that OVC and SETH have consequences for the theory of metric embeddings. For example, since
ℓd∞ -Furthest Pair can be solved in Õ(d · n) time, every n1.99 -time isometric embedding from n points in ℓd2
into ℓ∞ with d = ω (log log n)2 must blow up the dimension doubly-exponentially to n1−o(1) — unless OVC
and SETH are false. This is striking when one remembers that every n-point metric can be (efficiently)
isometrically embedded into ℓ∞ with n − 1 dimensions (by the classical Frechet embedding).
Unfortunately, the above conditional lower bounds only hold for exact solutions to the problems. Our
reductions from OV to closest/furthest pair no longer work if we only have (1 + ε )-approximations to the
closest/furthest pair (if they did, this paper would be about how OVC is false, thanks to many fast approximation algorithms for these problems [AI17]).
Hardness for All-Nearest Neighbors. The best known algorithms for the ℓ2 -Closest Pair problem are
nearly-linear, running in 2O(d) n logO(1) n time. A prominent open problem is whether the exponential dependence on d is necessary: Does ℓ2 -Closest Pair require n2−o(1) time in ω (log n) dimensions? Could we show
hardness under (for example) OVC or SETH?
The question is rather subtle. As mentioned earlier, the related problems of Bichromatic ℓ2 -Closest Pair
and ℓ2 -Furthest Pair are easily shown to be OV-hard in ω (log n) dimensions [Wil05, AW15]. Intuitively
speaking, in both of the latter problems, our reductions can “control” the distances between points in such a
way that it is easy to encode OV. But for ℓ2 -Closest Pair (with no colors), we have much less control, and it
is difficult to keep large sets of points far enough apart to successfully encode an OV instance [DSL16].
Here we report some progress on this open problem. In the closely-related All-Nearest Neighbors problem, the task is to report the ℓ2 -closest pair for all points in the given set. Nearly-linear algorithms are also
known for All-Nearest Neighbors, which have essentially the same complexity as ℓ2 -Closest Pair [Cla83,
Vai89]. We can show OV-hardness for All-Nearest Neighbors:
3

ω (log n)

Theorem 1.3. Under OVC, the All-Nearest Neighbors problem in ℓ2
stricted to vectors with entries from {−1, 0, 1}.

requires n2−o(1) time, even re-

The reduction goes through the Set Containment problem (equivalent to OV), and uses error-correcting
codes to keep one half of the vectors “distant” from each other, and the other half relatively “close” to the
first half.

2 A Dimensionality Self-Reduction for Orthogonal Vectors
In this section, we set up the framework for proving hardness for the aforementioned “barely-subquadratic”
problems. We begin with the following more general theorem, which will imply the dimensionality reduction lemma.
Theorem 2.1. For every d and integer ℓ ∈ [1, d], given two sets of vectors U,V ⊆ {0, 1}d , there is a deterministic algorithm running in n · d O(d/ℓ) time which outputs a list of t = d O(d/ℓ) integers {k1 , . . . , kt } ⊆ [0,t],
along with sets U ′ ,V ′ ⊆ Zℓ+1 such that |U ′ | = |U |, |V ′ | = |V |, and all entries in u′ , v′ are O((d log d)/ℓ)-bit
integers. There is an orthogonal pair u ∈ U, v ∈ V if and only if there is a pair u′ ∈ U ′ , v′ ∈ V ′ such that
hu′ , v′ i = ki for some i.
Although it may be difficult to see
√ in hindsight, the proof of Theorem 2.1 is inspired by the Merlin-Arthur
communication protocol with Õ( d) communication for Inner Product, due to Aaronson and Wigderson [AW09]. In that protocol, two parties each hold a d-bit vector, and
√ they wish to determine if their
vectors are orthogonal. The protocol shows how a √
prover can send an Õ( d)-bit message to the two parties,
to determine
such that the two parties only need to exchange Õ( d)-bits (with O(log d) public randomness)
√
orthogonality with high probability. They do this by encoding d-bit vectors with O( d)-degree bivariate
polynomials, and their protocol uses the key good property of low-degree polynomials that we know (they
have few roots, so evaluating distinct two polynomials at a random point will yield two distinct values, with
decent probability).
In the below proof of Theorem 2.1, there are several major differences. First, we forget one of the
variables, and encode our d-bit vectors with ℓ-dimensional vectors whose entries are d/ℓ-degree univariate
polynomials. Second, the parameter ℓ allows for a trade-off between the length of the vector and the degrees
of the polynomials. (This corresponds to a trade-off between the length of the prover’s message and the
length of the others’ messages, in the Merlin-Arthur protocol.) Third, we do not pick random points to
evaluate the polynomial on, but rather a single deterministic value. This actually suffices for our purposes.
Proof. Without loss of generality, assume d is a multiple of ℓ, otherwise we can add zeroes at the end of
each vector to satisfy this assumption.
Consider two vectors u ∈ U, v ∈ V . Divide the d dimensions of both vectors into ℓ contiguous blocks,
each of which contains d/ℓ dimensions. Suppose the ith block of u is [ui,1 , . . . , ui,d/ℓ ] and the ith block of v
is [vi,1 , . . . , vi,d/ℓ ], where all ui, j , vi, j ∈ {0, 1}. Construct the polynomials
d/ℓ

Pu,i (x) =

∑ ui, j · x j−1

j=1

and
d/ℓ

Qv,i (x) =

∑ vi, j · xd/ℓ− j .

j=1

4

Let Pu (x) be the ℓ-dimensional vector [Pu,1 , . . . , Pu,ℓ ] and Qv (x) be the ℓ-dimensional vector [Qv,1 , . . . , Qv,ℓ ].
Observe that the coefficient of xd/ℓ−1 in the polynomial Ru,v (x) = hPu (x), Qv (x)i is exactly
ℓ d/ℓ

∑ ∑ ui, j · vi, j = hu, vi .

i=1 j=1

Furthermore, note that for any u ∈ U and v ∈ V , the polynomial Ru,v (x) has degree at most 2d/ℓ, and each
of its coefficients are integers in [0, d].
Now we are ready to describe the reduction. First, enumerate all t = d O(d/ℓ) polynomials R(x) of degree
at most 2d/ℓ with coefficients in [0, d] ∩ Z such that the coefficient of xd/ℓ−1 equals 0.
Set x0 := d + 1. Note that, given the integer value k = R(x0 ) = ∑ℓ−1
i=0 Pu,i (x0 ) · Qv,i (x0 ), the polynomial
R(x) is uniquely determined, because all of its coefficients are integers in [0, d].
For all u ∈ U and v ∈ V , compute u′ := Pu (x0 ) and v′ := Qv (x0 ), creating two sets of vectors U ′ and V ′
where all vectors have ℓ dimensions, with entries of bit length at most O((d log d)/ℓ).
By enumerating over all such polynomials R(x), we obtain sets U ′ , V ′ , and collection of t integers
{R(x0 )} each in O(d log d)/ℓ bits, satisfying the conclusion of the theorem. In particular, the vectors u ∈ U ,
v ∈ V satisfy hu, vi = 0 if and only if there is some polynomial R(x) of degree at most 2d/ℓ with coefficients
in [0, d] ∩ Z such that hPu (x0 ), Qv (x0 )i = R(x0 ).
Now we prove the dimensionality reduction lemma:
Reminder of Lemma 1.1 [Dimensionality Reduction for OV] Let ℓ ∈ [1, d]. There is an n · d O(d/ℓ) -time
reduction from OV for n points in {0, 1}d to d O(d/ℓ) instances of OV for n points in Zℓ+1 , with vectors of
O(log n)-bit entries.
Proof. Given a set S of n (non-zero) vectors in {0, 1}d , set U := S and V := S in Theorem 2.1, which
produces n vectors U ′ and V ′ in Zℓ along with a set of d O(d/ℓ) numbers T such that S has an orthogonal pair
if and only if there is some u ∈ U ′ , v ∈ V ′ , and k ∈ T such that hu, vi = k.
For every k ∈ T , create new sets of vectors Uk′ ,Vk′ , where every u ∈ U ′ is replaced by uk := [u, 1] in Uk′ ,
and every v ∈ V ′ is replaced by vk := [v, −k] in Vk′ . Since all entries in u and v are non-negative, we observe:
1. for all u ∈ U ′ and v ∈ V ′ , hu, vi = k if and only if huk , vk i = 0,
2. for every pair uk , u′k ∈ Uk , uk , u′k ≥ 1, and
3. for every pair vk , v′k ∈ Vk , vk , v′k ≥ k2 .

Consider the set Sk := Uk ∪ Vk ⊂ Zℓ . By the above three facts, we could only obtain an orthogonal pair of
vectors in Sk by taking one vector from Uk and one vector from Vk , and Sk contains an orthogonal pair if and
only if there is some u ∈ U ′ and v ∈ V ′ such that hu, vi = k. Our reduction calls OV on Sk for every k ∈ T ,
and outputs the relevant orthogonal pair for S if any of the calls return an orthogonal pair for some Sk .

2.1 Consequences
Here we show how the above Dimensionality Reduction for OV implies hardness for the barely-subquadratic
problems mentioned in the introduction.
Reminder of Theorem 1.1 [Hardness of Hopcroft’s Problem] Under SETH (or OVC), Hopcroft’s problem
in ω (log log n) dimensions requires n2−o(1) time, with vectors of O(log n)-bit entries.
5

Proof. Let c ≥ 1 be an arbitrary constant and let d := c log n. We show how an oracle for Hopcroft’s problem
in ω (log log n) dimensions, running in O(n2−δ ) time for some universal δ > 0, can be used to solve OV for
n vectors in d dimensions in n2−δ +ε time (regardless of c) for every ε > 0, which would refute the OVC.
Set ℓ := c(log d)/α = c log(c log n)/α , for a small parameter α > 0 to be set later. Applying Lemma 1.1
to a given subset S ⊆ {0, 1}d , the reduction runs in time
n · (c log n)O(clog n)/ℓ) ≤ n · cO(α log n) ≤ n1+O(α log(c)) ,
and produces nO(α log(c)) instances of OV with n points in Z(clog log n)/α +O(1) , with vectors of O(log n)-bit
entries. Setting α ≪ ε / log(c), the reduction generates O(nε ) instances in Ω(1/ε · c log(c) · log log n) dimensions, each of which our Hopcroft oracle solves in n2−δ time, by assumption. This concludes the proof.
Reminder of Theorem 1.2 [Hardness of ℓ2 -Furthest Pair] Under SETH (or OVC), finding a ℓ2 -furthest pair
in ω (log log n)2 dimensions requires n2−o(1) time, with vectors of O(log n)-bit entries.
Proof. Given a fast algorithm for ℓ2 -furthest pair in ω (log log n)2 dimensions, we show how to quickly solve
Hopcroft’s problem on n points in ω (log log n) dimensions, and appeal to Theorem 1.1.
Let S be a set of n vectors in Zℓ with ℓ = ω (log log n) and with O(log n)-bit entries. Let k > 1 be such that
every entry of every vector has magnitude less than nk . In the following, let v[i] denote the ith component of
a vector v.
For every vector u ∈ S, define the (ℓ2 + 2)-dimensional vector
u′ := [u[1] · u[1], u[1] · u[2], . . . , u[i] · u[ j], . . . , u[ℓ] · u[ℓ], 0, n2k+1 ].
That is, the first ℓ2 components of u′ are all possible products of two components of u, followed by the
entries 0 and n2k+1 . Put each u′ in a set U ′ . Also for every vector v ∈ S, define the (ℓ2 + 2)-dimensional
vector
v′ := [v[1] · v[1], v[1] · v[2], . . . , v[i] · v[ j], . . . , v[ℓ] · v[ℓ], n2k+1 , 0],
and put v′ in a set V ′ . Now observe that:

• for u′1 , u′2 ∈ U ′ coming from some u1 , u2 ∈ S, hu′1 , u′2 i = ∑i, j∈[ℓ] u1 [i]u1 [ j]u2 [i]u2 [ j] + n4k+2 .
• for v′1 , v′2 ∈ V ′ coming from some v1 , v2 ∈ S, hv′1 , v′2 i = ∑i, j∈[ℓ] v1 [i]v1 [ j]v2 [i]v2 [ j] + n4k+2 .
Note that by our choice of k, |u1 [i]u1 [ j]u2 [i]u2 [ j]| ≤ n4k for all i, j. So all inner products are positive, in both
of the above cases. In contrast, for u′ ∈ U ′ and v′ ∈ V ′ ,
hu′ , v′ i =

∑
i, j∈[ℓ]

u[i]u[ j]v[i]v[ j] = ∑ u[i]v[i] · u[ j]v[ j] = (hu, vi)2 .
i, j

Now, all possible inner products between every u′ ∈ U ′ and v′ ∈ V ′ are non-negative, and hu′ , v′ i = 0 if and
only if hu, vi = 0.
Suppose we normalize all vectors in U ′ and V ′ , replacing each vector u′ and v′ by u′′ := u′ /||u′ ||2 . Since
hu′′ , v′′ i =

1
hu, vi,
||u′ ||2 · ||v′ ||2

6

the vector pairs in U ′ ,V ′ with zero inner product are exactly preserved, and all inner products of pairs within
U ′ (and of pairs within V ′ ) are still positive. By the law of cosines, for all u′′ ∈ U ′ and v′′ ∈ V ′ we have
||u′′ − v′′ ||22 = ||u′′ ||22 − ||v′ ||22 − 2hu′′ , v′′ i = 2 − 2hu′′ , v′′ i.
Therefore, taking S √
:= U ′ ∪ V ′ , solving Hopcroft’s problem on S is equivalent to finding two vectors with
ℓ2 -distance at least 2, and this is the maximum possible distance between two vectors in the instance. It
follows that solving ℓ2 -furthest pair on these instances will solve Hopcroft’s problem on them as well.
Corollary 2.1 (Hardness of Bichromatic ℓ2 -Closest Pair). Under SETH (or OVC), finding a bichromatic
ℓ2 -closest pair in ω (log log n)2 dimensions requires n2−o(1) time, with vectors of O(log n)-bit entries.
Proof. As before, we begin from the proof of hardness for Hopcroft’s problem (Theorem 1.1). The reduction
there computes O(nε ) instances of Hopcroft’s problem on n points in Ω(1/ε · c log(c) · log log n) dimensions,
for any desired ε > 0. We will slightly modify the proof of Theorem 1.2 for furthest pair to work for
bichromatic closest pair.
Let S be a set of n vectors in Zℓ with ℓ = ω (log log n) and O(log n)-bit entries. We wish to know if two
vectors in S are orthogonal.
Let v[i] denote the ith component of a vector v. We define the vectors in U ′ very similarly to the proof
of Theorem 1.2: for all u ∈ S, make the ℓ2 -dimensional vector
u′ := [u[1] · u[1], u[1] · u[2], . . . , u[i] · u[ j], . . . , u[ℓ] · u[ℓ]].
That is, each component of u′ is a product of two components of u. Put each u′ in a set U ′ of red points. For
every vector v ∈ S, define the ℓ2 -dimensional vector
v′ := [−v[1] · v[1], −v[1] · v[2], . . . , −v[i] · v[ j], . . . , −v[ℓ] · v[ℓ]],
and put v′ in a set V ′ of blue points. Now observe that for every red u′ ∈ U ′ and every blue v′ ∈ V ′ ,
u′ , v′ = −(hu, vi)2 .
Thus the inner product between a red u′ and a blue v′ is zero when hu, vi = 0, and is otherwise negative. If
we normalize all vectors in U ′ and V ′ , those red-blue pairs with zero inner product are preserved, and the
rest of the red-blue pairs still have negative inner product. Analogously
√ as in Theorem 1.2, this means that
the red-blue pairs with zero √
inner product have Euclidean distance 2, and all other red-blue pairs have
distance strictly greater than 2. Therefore finding the closest red-blue pair in this ℓ2 -dimensional instance
will solve the original instance S of Hopcroft’s problem.

3 Hardness of Euclidean All-Nearest Neighbors
Here we prove hardness for All-Nearest Neighbors in ω (log n) dimensions:
ω (log n)

Reminder of Theorem 1.3 Under OVC, the All-Nearest Neighbors problem in ℓ2
requires n2−o(1)
time, even restricted to vectors with entries from {−1, 0, 1}.
It seems plausible that there is a sub-quadratic-time reduction from All-Nearest Neighbors to ℓ2 -Closest
Pair (even in high dimensions), so we think of Theorem 1.3 as good evidence that ℓ2 -Closest Pair is also
hard for ω (log n) dimensions.
7

Proof. Let d = O(log n). We begin with the Subset Containment problem: Given n red subsets of [d] and n
blue subsets of [d], is there some red subset that is contained in some blue subset? It is well-known that this
problem is equivalent to OV on n vectors in d dimensions [Wil05] (imagine you have a red/blue version of
OV with vectors in {0, 1}d , and flip all the bits of the blue vectors; this converts the OV instance to a Subset
Containment instance).
The main idea of the proof is to use error correcting codes over {−1, 1} to keep the red points “far apart”
from each other, so that the nearest neighbor of each red point x is a blue point y which is as close to being
a superset of x as possible.
Let R be the collection of red sets and let B be the blue sets. We will think of them as vectors in {0, 1}d
in the natural way. First, we do a trick which will help control the vector norms. Try all pairs of integers
d1 , d2 ∈ [d] with d1 < d2 . Take the subset Rd1 of R which only contains vectors having exactly d1 ones,
and take the subset Bd2 of B which only contains vectors having exactly d2 ones. We will work with the
collections R′ := Rd1 and B′ := Bd2 in the following. (The benefit is that we now may assume that all red
vectors have the same norm value vA , and all blue vectors have the same norm value vB , and it only costs
O(d 2 ) extra calls.)
Let ε ∈ (0, 1/2). We say that a code with distance at least (1/2 − ε ) is a collection of vectors S ⊆
{−1, 1}k such that for all u, v ∈ S with u 6= v, hu, vi ≤ 2ε k. Note this condition is equivalent to saying
that the Hamming distance between each pair of k-dimensional vectors is at least (1/2 − ε )k. Such codes
are known to have polynomial-time constructions. In particular, it was recently shown how to efficiently
construct a set S of at least n such vectors, with dimension only k ≤ t = O(log n)/ε 2+o(1) [TS17]. In the
following, let S be such a code with ε = 1/8 and the dimension k as a parameter to be set later.
We will add k dimensions to all vectors in R′ and B′ . For each vector vi ∈ R, for i = 1, . . . , n, we
concatenate the ith codeword from S to the end of it, obtaining a (d + k)-dimensional vector v′i . For each
vector wi ∈ B, we concatenate k zeroes to the end, obtaining a (d + k)-dimensional w′i .
Observe that for all vectors v′i from R′ , their ℓ2 -norm squared is
k

||v′i ||22 = d1 + ∑ 22 = d1 + 4k

(1)

i=1

For all vectors w′i from B′ , we have ||w′i ||22 = d2 . Furthermore, observe that for every two vectors v′i , v′j from
R′ , their inner product is at most (d1 − 1) + 2ε k, because the original vectors vi and v j were distinct vectors
with exactly d1 ones (so their inner product is at most d1 − 1), and the inner product of any two distinct
codewords is at most 2ε k. Therefore we have
||v′i − v′j ||22 = ||v′i ||22 + ||v′j ||22 − 2 v′i , v′j
= 2(d1 + 4k) − 2 v′i , v′j

(by (1))

≥ 2(d1 + 4k) − 2(d1 − 1 + 2ε k) = 8k + 2 − 4ε k = (8 − 1/2)k + 2.
On the other hand, for a vector v′i from R′ and a vector w′j from B′ ,
||v′i − w′j ||22 = ||v′i ||22 + ||w′j ||22 − 2 v′i , w′j = d1 + 4k + d2 − 2 v′i , w′j .
E
D
Note that the inner product v′i , w′j is maximized when the original subset vi (of cardinality d1 ) is contained
D
E
in the subset w j (of cardinality d2 ), in which case v′i , w′j = d1 . So the minimum possible distance between

v′i and w′j is

||v′i − w′j ||22 = d1 + 4k + d2 − 2 v′i , w′j = (d2 − d1 ) + 4k.
8

Putting it all together, suppose we set k large enough that
(8 − 1/2)k + 2 > d + 4k
(e.g. k ≥ d will do). From there, if there is some red set (of cardinality d1 ) in R contained in a blue set (of
cardinality d2 ) in B, then the nearest neighbor of the corresponding point in R′ will be a point in B′ with
distance precisely (d2 − d1 ) + 4k from it. Set k = Θ(log n) so that it is at least d, and it is large enough to
support at least n distinct codewords with ε = 1/8.
We have reduced OV with n vectors in {0, 1}clog n to n points in {−1, 0, 1}Θ(log n) , such that computing
all-nearest neighbors in ℓ2 will determine if the original instance had a red set contained in a blue set. In
particular, we can check for every point whether its nearest neighbor corresponds to a set containing it in the
original instance, or a set it contains. By the above, there is a red set contained in a blue set if and only if
for the cardinalities d1 and d2 of these respective sets, the nearest neighbor to some point v in Rd1 is a point
in Bd2 with distance only (d2 − d1 ) + 4k from v.

4 Conclusion
We have given some rigorous explanation for why certain point-location and proximity problems only admit barely-subquadratic time algorithms: they can encode difficult high-dimensional Boolean problems in
surprisingly low dimensions. In contrast, the nearly-linear proximity problems seem incapable of such an
encoding; moreover, if any of them were found to be capable, we would be refuting some major conjectures
in fine-grained complexity.
It is likely that many more consequences can be derived than what we have shown here.
• For one example, Backurs and Indyk (personal communication) have noticed that our lower bound for
bichromatic ℓ2 -Closest Pair implies an inapproximability result for the fast Gauss transform [GS91],
where we are given a set of n red vectors R and n blue vectors B in Rd , and are asked to compute
F(r) =

2

∑ e−||a−b||
b∈B

for every r ∈ R. In particular, they have observed that (under OVC) F cannot be approximated with
an additive ε -error in n2−δ · poly(log(1/ε ), 2d ) time, for any fixed δ > 0.
• For another example, a variant of the reduction in Lemma 1.1 (where instead of setting x := d + 1 in
the polynomials, we imagine trying all choices for x from a large-enough field, and we build largerdimensional Boolean vectors whose inner products model the process of computing inner products
among all values of x) was used in recent work with Abboud and Rubenstein [ARW17] to show that
finding a vector pair of maximum inner product among a set of n Boolean no(1) -dimensional vectors
is hard to non-trivially approximate in sub-quadratic time.
There are many interesting questions to pursue further; here are some particularly compelling ones.
1. Can the ω (log log n) and ω (log log n)2 dimensionality in our hardness reductions be reduced, all the
way down to ω (1) dimensions? This would demonstrate very tight hardness for solving these problems. The main bottleneck is that in the main reduction (Theorem 2.1 and Lemma 1.1) it seems
we have to compute O(log n)O(log n)/ℓ different instances to go from O(log n) dimensions down to ℓ
dimensions; perhaps there is a more efficient reduction method.
9

2. All of the nearly-linear problems discussed in this paper actually have 2O(d) · n logO(1) n-time algorithms, except for bichromatic ℓ1 and ℓ∞ closest pair, for which their best known algorithms have the
running time bound n · logO(d) n. Could stronger hardness be established for these two problems, or
can their dependence on d be improved? So far, prior work [Wil05, DSL16] has only established
quadratic-time hardness for these problems when d = ω (log n), so it is quite possible that they are in
fact solvable in 2O(d) · n logO(1) n time, like the other nearly-linear problems.
3. The All-Nearest Neighbors problem is solvable in 2O(d) · n logO(1) n time in the general case, not
just when all vectors are in {−1, 0, 1}. Is there is a dimensionality reduction for the special case
of {−1, 0, 1}, similar to Lemma 1.1? (Please note that this would likely refute OVC and SETH.)
4. Do any of the “popular conjectures” in fine-grained complexity imply that ℓ2 -Closest Pair requires
n2−o(1) time in ω (log n) dimensions?

Acknowledgements
I am grateful to Amir Abboud, Arturs Backurs, Piotr Indyk, Aviad Rubenstein, and Huacheng Yu for useful
comments and discussions. In particular, several years ago Huacheng took patient notes from one of our
meetings, and wrote up a version of the main lemma presented here. Unfortunately he declined to be an
author on this paper.

References
[AESW91] Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. Euclidean
minimum spanning trees and bichromatic closest pairs. In Discrete and Computational Geometry, pages 407–422. ACM, 1991.
[AI17]

Alexandr Andoni and Piotr Indyk. Nearest neighbors in high-dimensional spaces. In Jacob E.
Goodman, Joseph O’Rourke, , and Csaba D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press, 2017.

[ARW17]

Amir Abboud, Aviad Rubenstein, and Ryan Williams. Distributed PCP theorems for hardness
of approximation in P. In FOCS, page to appear, 2017.

[AVW14]

Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster
alignment of sequences. In ICALP, pages 39–51, 2014.

[AW09]

Scott Aaronson and Avi Wigderson. Algebrization: A new barrier in complexity theory. ACM
TOCT, 1, 2009.

[AW15]

Josh Alman and Ryan Williams. Probabilistic polynomials and hamming nearest neighbors. In
FOCS, 2015.

[AWY15]

Amir Abboud, Richard Ryan Williams, and Huacheng Yu. More applications of the polynomial
method to algorithm design. In SODA, pages 218–230, 2015.

[BS76]

Jon Louis Bentley and Michael Ian Shamos. Divide-and-conquer in multidimensional space. In
STOC, pages 220–230. ACM, 1976.
10

[Cha93]

Bernard Chazelle. Cutting hyperplanes for divide-and-conquer. Discrete & Computational
Geometry, 9:145–158, 1993.

[Cha17]

Timothy M. Chan. Orthogonal Range Searching in Moderate Dimensions: k-d Trees and Range
Trees Strike Back. In SOCG, volume 77 of Leibniz International Proceedings in Informatics
(LIPIcs), pages 27:1–27:15, 2017.

[CIP09]

Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of satisfiability
of small depth circuits. In Parameterized and Exact Complexity (IWPEC), pages 75–85, 2009.

[Cla83]

Kenneth L. Clarkson. Fast algorithms for the all nearest neighbors problem. In FOCS, pages
226–232. IEEE, 1983.

[CW16]

Timothy M. Chan and Ryan Williams. Deterministic APSP, Orthogonal Vectors, and more:
Quickly derandomizing Razborov-Smolensky. In SODA, pages 1246–1255, 2016.

[DHKP97] Martin Dietzfelbinger, Torben Hagerup, Jyrki Katajainen, and Martti Penttonen. A reliable
randomized algorithm for the closest-pair problem. Journal of Algorithms, 25(1):19–51, 1997.
[DL97]

Michel Marie Deza and Monique Laurent. Geometry of Cuts and Metrics. Springer, 1997.

[DSL16]

Roee David, Karthik C. S., and Bundit Laekhanukit. On the complexity of closest pair via
polar-pair of point-sets. CoRR, abs/1608.03245, 2016.

[Eri95]

Jeff Erickson. On the relative complexities of some geometric problems. In Proceedings of the
7th Canadian Conference on Computational Geometry, pages 85–90, 1995.

[Eri96]

Jeff Erickson. New lower bounds for Hopcroft’s problem. Discrete & Computational Geometry,
16(4):389–418, 1996.

[GBT84]

Harold N. Gabow, Jon Louis Bentley, and Robert E. Tarjan. Scaling and related techniques for
geometry problems. In STOC, pages 135–143. ACM, 1984.

[GLR10]

Venkatesan Guruswami, James R Lee, and Alexander Razborov. Almost euclidean subspaces
of ℓ1 via expander codes. Combinatorica, 30(1):47–68, 2010.

[GS91]

Leslie Greengard and John Strain. The fast gauss transform. SIAM Journal on Scientific and
Statistical Computing, 12(1):79–94, 1991.

[Ind07]

Piotr Indyk. Uncertainty principles, extractors, and explicit embeddings of ℓ2 into ℓ1 . In STOC,
pages 615–620. ACM, 2007.

[IP01]

Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst.
Sci., 62(2):367–375, 2001.

[KM95]

Samir Khuller and Yossi Matias. A simple randomized sieve algorithm for the closest-pair
problem. Information and Computation, 118(1):34–37, 1995.

[Knu73]

Donald Ervin Knuth. The art of computer programming: sorting and searching, volume 3.
Pearson Education, 1973.

11

[LLR94]

Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its
algorithmic applications. In FOCS, pages 577–591. IEEE, 1994.

[Mat93]

Jirı́ Matousek. Range searching with efficient hiearchical cutting. Discrete & Computational
Geometry, 10:157–182, 1993.

[MP69]

Marvin Minsky and Seymour Papert. Perceptrons: An Introduction to Computational Geometry. The MIT Press, 1969.

[PS85]

Franco P Preparata and Michael Ian Shamos. Computational Geometry: An Introduction.
Springer, 1985.

[TS17]

Amnon Ta-Shma. Explicit, almost optimal, epsilon-balanced codes. In STOC, 2017.

[Vai89]

Pravin M. Vaidya. An o(n log n) algorithm for the all-nearest-neighbors problem. Discrete &
Computational Geometry, 4(1):101–115, 1989.

[Wil05]

Ryan Williams. A new algorithm for optimal 2-constraint satisfaction and its implications.
Theor. Comput. Sci., 348(2-3):357–365, 2005.

[WW75]

J. H. Wells and L. R. Williams. Embeddings and extensions in analysis. Springer-Verlag, 1975.

[WY14]

Ryan Williams and Huacheng Yu. Finding orthogonal vectors in discrete structures. In SODA,
pages 1867–1877, 2014.

[Yao82]

Andrew Chi-Chih Yao. On constructing minimum spanning trees in k-dimensional spaces and
related problems. SIAM Journal on Computing, 11(4):721–736, 1982.

12

