lemmatheorem corollarytheorem definitiontheorem claimtheorem
propositiontheorem remarktheorem hypothesistheorem observationtheorem
conjecturetheorem lemma remark corollary proposition definition claim
hypothesis observation

# Tight Lower Bounds for Approximate & Exact $k$-Center in
$\mathbb{R}^{d}$††thanks: An extended abstract of this paper appears in SoCG
2022.

Rajesh Chitnis  Nitin Saurabh  Indian Institute of Technology Hyderabad,
Sangareddy, India<EMAIL_ADDRESS>
###### Abstract

In the discrete $k$-Center problem, we are given a metric space
$(P,\texttt{dist})$ where $|P|=n$ and the goal is to select a set $C\subseteq
P$ of $k$ centers which minimizes the maximum distance of a point in $P$ from
its nearest center. For any $\epsilon>0$, Agarwal and Procopiuc [SODA ’98,
Algorithmica ’02] designed an $(1+\epsilon)$-approximation algorithm111The
algorithm of Agarwal and Procopiuc [2] also works for the non-discrete, i.e.,
continuous, version of the problem when $C$ need not be a subset of $P$, but
our lower bounds only hold for the discrete version. for this problem in
$d$-dimensional Euclidean space222The algorithm of Agarwal and Procopiuc [2]
also works for other metrics such as $\ell_{\\_}{\infty}$ or $\ell_{\\_}q$
metric for $q\geq 1$. Our construction also works for $\ell_{\\_}{\infty}$ (in
fact, some of the bounds are simpler to derive!) but we present only the proof
for $\ell_{\\_}2$ to keep the presentation simple. which runs in $O(dn\log
k)+\left(\dfrac{k}{\epsilon}\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$
time. In this paper we show that their algorithm is essentially optimal: if
for some $d\geq 2$ and some computable function $f$, there is an
$f(k)\cdot\left(\dfrac{1}{\epsilon}\right)^{o\left(k^{1-1/d}\right)}\cdot
n^{o\left(k^{1-1/d}\right)}$ time algorithm for $(1+\epsilon)$-approximating
the discrete $k$-Center on $n$ points in $d$-dimensional Euclidean space then
the Exponential Time Hypothesis (ETH) fails.

We obtain our lower bound by designing a gap reduction from a $d$-dimensional
constraint satisfaction problem (CSP) to discrete $d$-dimensional $k$-Center.
This reduction has the property that there is a fixed value $\epsilon$
(depending on the CSP) such that the optimal radius of $k$-Center instances
corresponding to satisfiable and unsatisfiable instances of the CSP is $<1$
and $\geq(1+\epsilon)$ respectively. Our claimed lower bound on the running
time for approximating discrete $k$-Center in $d$-dimensions then follows from
the lower bound due to Marx and Sidiropoulos [SoCG ’14] for checking the
satisfiability of the aforementioned $d$-dimensional CSP.

As a byproduct of our reduction, we also obtain that the exact algorithm of
Agarwal and Procopiuc [SODA ’98, Algorithmica ’02] which runs in
$n^{O\left(d\cdot k^{1-1/d}\right)}$ time for discrete $k$-Center on $n$
points in $d$-dimensional Euclidean space is asymptotically optimal. Formally,
we show that if for some $d\geq 2$ and some computable function $f$, there is
an $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time exact algorithm for the
discrete $k$-Center problem on $n$ points in $d$-dimensional Euclidean space
then the Exponential Time Hypothesis (ETH) fails. Previously, such a lower
bound was only known for $d=2$ and was implicit in the work of Marx [IWPEC
’06].

##  1 Introduction

The $k$-Center problem is a classical problem in theoretical computer science
and was first formulated by Hakimi [21] in 1964. In this problem, given a
metric space $(P,\texttt{dist})$ and an integer $k\leq|P|$ the goal is to
select a set $C$ of $k$ centers which minimizes the maximum distance of a
point in $P$ from its nearest center, i.e., select a set $C$ which minimizes
the quantity $\max_{\\_}{p\in P}\min_{\\_}{c\in C}\texttt{dist}(p,c)$. A
geometric way to view the $k$-Center problem is to find the minimum radius $r$
such that $k$ closed balls of radius $r$ located at each of the points in $C$
cover all the points in $P$. In most applications, we require that $C\subseteq
P$ and this is known as the discrete version of the problem.

As an example, one can consider the set $P$ to be important locations in a
city and solving the $k$-Center problem (where $k$ is upper bounded by budget
constraints) establishes the locations of fire stations which minimize the
response time in event of a fire. In addition to other applications in
facility location, transportation networks, etc. an important application of
$k$-Center is in clustering. With the advent of massive data sets, the problem
of efficiently and effectively summarizing this data is crucial. A standard
approach for this is via centroid-based clustering algorithms of which
$k$-Center is a special case. Clustering using $k$-Center has found
applications in text summarization, robotics, bioinformatics, pattern
recognition, etc [40, 19, 22, 29].

###  1.1 Prior work on exact & approximate algorithms for discrete $k$-Center

The discrete333Here we mention the known results only for the discrete version
of $k$-Center. A discussion about results for the continuous version of the
problem is given in Section 1.4. $k$-Center problem is NP-hard [43], and
admits a $2$-approximation [23, 20] in $n^{O(1)}$ time where $n$ is the number
of points. This approximation ratio is tight and the $k$-Center problem is NP-
hard to approximate in polynomial time to a factor $(2-\epsilon)$ for any
constant $\epsilon>0$ [24, 20]. Given this intractability, research was aimed
at designing parameterized algorithms [9] and parameterized approximation
algorithms for $k$-center. The $k$-Center problem is W[2]-hard to approximate
to factor better than $2$ even when allowing running times of the form
$f(k)\cdot n^{O(1)}$ for any computable function $f$ [14, 12]. The $k$-Center
problem remains W[2]-hard even if we combine the parameter $k$ with other
structural parameters such as size of vertex cover or size of feedback vertex
set [30]. Agarwal and Procopiuc [2] designed an algorithm for discrete
$k$-Center on $n$ points in $d$-dimensional Euclidean space which runs in
$n^{O\left(d\cdot k^{1-1/d}\right)}$ time.

The paradigm of combining parameterized algorithms & approximation algorithms
has been successful in designing algorithms for $k$-center in special
topologies such as $d$-dimensional Euclidean space [2], planar graphs [18],
metrics of bounded doubling dimensions [15], graphs of bounded highway
dimension [14, 4], etc. Of particular relevance to this paper is the
$(1+\epsilon)$-approximation algorithm444This is also known as an efficient
parameterized approximation scheme (EPAS) as the running time is a function of
the type $f(k,\epsilon,d)\cdot n^{O(1)}$. of Agarwal and Procopiuc [2] which
runs in $O(dn\log
k)+\left(\dfrac{k}{\epsilon}\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$
time. This was generalized by Feldmann and Marx [15] who designed an
$(1+\epsilon)$-approximation algorithm running in
$\left(\dfrac{k^{k}}{\epsilon^{O(kD)}}\right)\cdot n^{O(1)}$ time for discrete
$k$-Center in metric spaces of doubling dimension $D$.

###  1.2 From 2-dimensions to higher dimensions

##### Square root phenomenon for planar graphs and geometric problems in the
plane:

For a wide range of problems on planar graphs or geometric problems in the
plane, a certain square root phenomenon is observed for a wide range of
algorithmic problems: the exponent of the running time can be improved from
$O(\ell)$ to $O(\sqrt{\ell})$ where $\ell$ is the parameter, or from $O(n)$ to
$O(\sqrt{n}$) where $n$ is in the input size, and lower bounds indicate that
this improvement is essentially best possible. There is an ever increasing
list of such problems known for planar graphs [7, 34, 31, 39, 32, 13, 41, 37,
33, 1, 17] and in the plane [37, 35, 16, 3, 42, 26, 25]

##### Bounds for higher dimensional Euclidean spaces:

Unlike the situation on planar graphs and in two-dimensions, the program of
obtaining tight bounds for higher dimensions is still quite nascent with
relatively fewer results [8, 38, 5, 11, 10]. Marx and Sidiropoulos [38] showed
that for some problems there is a _limited blessing of low dimensionality_ :
that is, for $d$-dimensions the running time can be improved from $n^{\ell}$
to $n^{\ell^{1-1/d}}$ or from $2^{n}$ to $2^{n^{1-1/d}}$ where $\ell$ is a
parameter and $n$ is the input size. In contrast, Cohen-Addad et al. [8]
showed that the two problems of $k$-Median and $k$-Means suffer from the
_curse of low dimensionality_ : even for $4$-dimensional Euclidean space,
assuming the Exponential Time Hypothesis555Recall that the Exponential Time
Hypothesis (ETH) has the consequence that $n$-variable 3-SAT cannot be solved
in $2^{o(n)}$ time [27, 28]. (ETH), there is no $f(k)\cdot n^{o(k)}$ time
algorithm, i.e., the brute force algorithm which runs in $n^{O(k)}$ time is
asymptotically optimal.

###  1.3 Motivation & Our Results

In two-dimensional Euclidean space there is an $n^{O(\sqrt{k})}$ algorithm [2,
26, 25], and a matching lower bound of $f(k)\cdot n^{o(\sqrt{k})}$ under
Exponential Time Hypothesis (ETH) for any computable function $f$ [35]. Our
motivation in this paper is to investigate what is the _correct_ complexity of
exact and approximate algorithms for the discrete $k$-Center for higher
dimensional Euclidean spaces. In particular, we aim to answer the following
two questions:

(Question 1) Can the running time of the $(1+\epsilon)$-approximation
algorithm of [2] be improved from $O(dn\log
k)+\left(\dfrac{k}{\epsilon}\right)^{O\left(k^{1-1/d}\right)}\cdot n^{O(1)}$,
or is there a (close to) matching lower bound? (Question 2) The
$n^{O\left(d\cdot k^{1-1/d}\right)}$ algorithm of [2] for $d$-dimensional
Euclidean space shows that there is a _limited blessing of low dimensionality_
for $k$-Center. But can the term $k^{1-1/d}$ in the exponent be improved, or
is it asymptotically tight?

We make progress towards answering both these questions by showing the
following theorem:

######  Theorem 1.

For any $d\geq 2$, under the Exponential Time Hypothesis (ETH), the discrete
$k$-Center problem in $d$-dimensional Euclidean space

\- (Inapproximability result)

does not admit an $(1+\epsilon)$-approximation in
$f(k)\cdot\left(\frac{1}{\epsilon}\right)^{o\left(k^{1-1/d}\right)}\cdot
n^{o\left(k^{1-1/d}\right)}$ time where $f$ is any computable function and $n$
is the number of points.

\- (Lower bound for exact algorithm)

cannot be solved in $f(k)\cdot n^{o\left(k^{1-1/d}\right)}$ time where $f$ is
any computable function and $n$ is the number of points.

Theorem 1 answers Question $1$ by showing that the running time of the
$(1+\epsilon)$-approximation algorithm of Agarwal and Procopiuc [2] is
essentially tight, i.e., the dependence on $\epsilon$ cannot be improved even
if we allow a larger dependence on both $k$ and $n$. Theorem 1 answers
Question $2$ by showing that the running time of the exact algorithm of
Agarwal and Procopiuc [2] is asymptotically tight, i.e., the exponent of
$k^{1-1/d}$ cannot be asymptotically improved even if we allow a larger
dependence on $k$.

###  1.4 Discussion of the continuous $k$-Center problem

In the continuous version of the $k$-Center problem, the centers are not
required to be picked from the original set of input points. The
$n^{O\left(d\cdot k^{1-1/d}\right)}$ algorithm of Agarwal and Procopiuc [2]
also works for this continuous version of the $k$-Center problem in
$\mathbb{R}^{d}$. Marx [36] showed the W[1]-hardness of $k$-Center in
$(\mathbb{R}^{2},\ell_{\\_}{\infty})$ parameterized by $k$. Cabello et al. [6]
studied the complexity of this problem parameterized by the dimension, and
showed the W[1]-hardness of $4$-Center in
$(\mathbb{R}^{d},\ell_{\\_}{\infty})$ parameterized by $d$. Additionally, they
also obtained the W[1]-hardness of $2$-Center in
$(\mathbb{R}^{d},\ell_{\\_}{2})$ parameterized by $d$; this reduction also
rules out existence of $n^{o(d)}$ algorithms for this problem under the
Exponential Time Hypothesis (ETH). It is an interesting open question whether
the $n^{O\left(d\cdot k^{1-1/d}\right)}$ algorithm of Agarwal and Procopiuc
[2] is also asymptotically tight for the continuous version of the problem:
one way to possibly prove this would be to extend the W[1]-hardness reduction
of Marx [36] for continuous $k$-Center in $\mathbb{R}^{2}$ (parameterized by
$k$) to higher dimensions using the framework of Marx and Sidiropoulos [38].
Our reduction in this paper does not extend to the continuous version.

###  1.5 Notation

The set $\\{1,2,\ldots,n\\}$ is denoted by $[n]$. All vectors considered in
this paper have length $d$. If $\mathbf{a}$ is a vector then for each
$i\in[d]$ its $i$-th coordinate is denoted by $\mathbf{a}[i]$. Addition and
subtraction of vectors is denoted by $\oplus$ and $\ominus$ respectively. The
$i$-th unit vector is denoted by $\mathbf{e}_{\\_}i$ and has
$\mathbf{e}_{\\_}{i}[i]=1$ and $\mathbf{e}_{\\_}{i}[j]=0$ for each $j\neq i$.
The $d$-dimensional vector whose every coordinate equals $1$ is denoted by
$\mathbf{1}^{d}$. If $u$ is a point and $X$ is a set of points then
$\texttt{dist}(u,X)=\min_{\\_}{x\in X}\texttt{dist}(u,x)$. We will sometimes
abuse notation slightly and use $x$ to denote both the name and location of
the point $x$.

##  2 Lower bounds for exact & approximate $k$-Center in $d$-dimensional
Euclidean space

The goal of this section is to prove Theorem 1 which is restated below:

See 1

##### Roadmap to prove Theorem 1:

To prove Theorem 1, we design a gap reduction (described in Section 2.2) from
a constraint satisfaction problem (CSP) to the $k$-Center problem. The
definition and statement of the lower bound for the CSP due to Marx and
Sidiropoulos [38] is given in Section 2.1. The correctness of the reduction is
shown in Section 2.3 and Section 2.4. Finally, everything is tied together in
Section 2.5 which contains the proof of Theorem 1.

###  2.1 Lower bound for $d$-dimensional geometric $\geq$-CSP [38]

This section introduces the $d$-dimensional geometric $\geq$-CSP problem of
Marx and Sidiropoulos [38]. First we start with some definitions before
stating the formal lower bound (Theorem 2) that will be used to prove Theorem
1. Constraint Satisfaction Problems (CSPs) are a general way to represent
several important problems in theoretical computer science. In this paper, we
will only need a subclass of CSPs called binary CSPs which we define below.

######  Definition .

An instance of a binary constraint satisfaction problem (CSP) is a triple
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ where $\mathcal{V}$ is a
set of variables, $\mathcal{D}$ is a domain of values and $\mathcal{C}$ is a
set of constraints. There are two types of constraints:

  * •

_Unary constraints_ : For some $v\in\mathcal{V}$ there is a unary constraint
$\langle v,R_{\\_}v\rangle$ where $R_{\\_}v\subseteq\mathcal{D}$.

  * •

_Binary constraints_ : For some $u,v\in\mathcal{V}$, $u\neq v$, there is a
binary constraint $\big{\langle}(u,v),R_{\\_}{u,v}\big{\rangle}$ where
$R_{\\_}{u,v}\subseteq\mathcal{D}\times\mathcal{D}$.

Solving a given CSP instance
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ is to check whether there
exists a satisfying assignment for it, i.e., a function
$f:\mathcal{V}\to\mathcal{D}$ such that all the constraints are satisfied. For
a binary CSP, a satisfying assignment $f$ has the property that for each unary
constraint $\langle v,R_{\\_}v\rangle$ we have $f(v)\in R_{\\_}v$ and for each
binary constraint $\big{\langle}(u,v),R_{\\_}{u,v}\big{\rangle}$ we have
$\left(f(u),f(v)\right)\in R_{\\_}{u,v}$.

The constraint graph of a given CSP instance $\mathcal{I}=(V,D,C)$ is an
undirected graph $G_{\\_}{\mathcal{I}}$ whose vertex set is $V$ and the
adjacency relation is defined as follows: two vertices $u,v\in V$ are adjacent
in $G_{\\_}{\mathcal{I}}$ if there is a constraint in $\mathcal{I}$ which
contains both $u$ and $v$. Marx and Sidiropoulos [38] observed that binary
CSPs whose primal graph is a subgraph of the $d$-dimensional grid are useful
in showing lower bounds for geometric problems in $d$-dimensions.

######  Definition .

The $d$-dimensional grid $\textup{R}[N,d]$ is an undirected graph with vertex
set $[N]^{d}$ and the adjacency relation is as follows: two vertices
$(a_{\\_}1,a_{\\_}2,\ldots,a_{\\_}d)$ and
$(b_{\\_}1,b_{\\_}2,\ldots,b_{\\_}d)$ have an edge between them if and only if
$\sum_{\\_}{i=1}^{d}|a_{\\_}i-b_{\\_}i|=1$.

######  Definition .

A $d$-dimensional geometric $\geq$-CSP
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ is a binary CSP whose

  * •

set of variables $\mathcal{V}$ is a subset of $\textup{R}[N,d]$ for some
$N\geq 1$,

  * •

domain is $[\delta]^{d}$ for some integer $\delta\geq 1$,

  * •

constraint graph $G_{\\_}{\mathcal{I}}$ is an _induced_ subgraph of
$\textup{R}[N,d]$,

  * •

unary constraints are arbitrary, and

  * •

binary constraints are of the following type: if
$\mathbf{a},\mathbf{a}^{\prime}\in\mathcal{V}$ such that
$\mathbf{a}^{\prime}=\mathbf{a}\oplus\mathbf{e}_{\\_}i$ for some $i\in[d]$
then there is a binary constraint
$\big{\langle}(\mathbf{a},\mathbf{a}^{\prime}),R_{\\_}{\mathbf{a},\mathbf{a}^{\prime}}\big{\rangle}$
where
$R_{\\_}{\mathbf{a},\mathbf{a}^{\prime}}=\left\\{\left(\mathbf{x},\mathbf{y}\right)\in
R_{\\_}{\mathbf{a}}\times R_{\\_}{\mathbf{a}^{\prime}}\ \mid\
\mathbf{x}[i]\geq\mathbf{y}[i]\right\\}$.

Observe that the set of unary constraints of a $d$-dimensional geometric
$\geq$-CSP is sufficient to completely define it. The size $|\mathcal{I}|$ of
a binary CSP $\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ is the
combined size of the variables, domain and the constraints. With appropriate
preprocessing (e.g., combining different constraints on the same variables) we
can assume that
$|\mathcal{I}|=\left(|\mathcal{V}|+|\mathcal{D}|\right)^{O(1)}$. We now state
the result of Marx and Sidiropoulos [38] which gives a lower bound on the
complexity of checking whether a given $d$-dimensional geometric $\geq$-CSP
has a satisfying assignment.

######  Theorem 2.

[38, Theorem 2.10] If for some fixed $d\geq 2$, there is an
$f(|\mathcal{V}|)\cdot|\mathcal{I}|^{o\left(|\mathcal{V}|^{1-1/d}\right)}$
time algorithm for solving a $d$-dimensional geometric $\geq$-CSP
$\mathcal{I}$ for some computable function $f$, then the Exponential Time
Hypothesis (ETH) fails.

######  Remark .

The problem defined by Marx and Sidiropoulos [38] is actually $d$-dimensional
geometric $\leq$-CSP which has $\leq$-constraints instead of the
$\geq$-constraints. However, for each $\mathbf{a}\in\mathcal{V}$ by replacing
each unary constraint $\mathbf{x}\in R_{\\_}{\mathbf{a}}$ by $\mathbf{y}$ such
that $\mathbf{y}[i]=N+1-\mathbf{x}[i]$ for each $i\in[d]$, it is easy to see
that $d$-dimensional geometric $\leq$-CSP and $d$-dimensional geometric
$\geq$-CSP are equivalent.

###  2.2 Reduction from $d$-dimensional geometric $\geq$-CSP to $k$-Center in
$\mathbb{R}^{d}$

We are now ready to describe our reduction from $d$-dimensional geometric
$\geq$-CSP to $k$-Center in $\mathbb{R}^{d}$. Fix any $d\geq 2$. Let
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ be a $d$-dimensional
geometric $\geq$-CSP instance on variables $\mathcal{V}$ and domain
$[\delta]^{d}$ for some integer $\delta\geq 1$. We fix666For simplicity of
presentation, we choose $r=1/4$ instead of $r=1$: by scaling the result holds
also for $r=1$. the following two quantities:

$\displaystyle
r:=\frac{1}{4}\quad\text{and}\quad{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\epsilon:=\frac{r^{2}}{(d-1)\delta^{2}}=\frac{1}{16(d-1)\delta^{2}}}.$
(1)

Since $d\geq 2$ and $\delta\geq 1$, we obtain the following bounds from
Equation 1,

$\displaystyle
0<\epsilon\leq\epsilon\delta\leq\epsilon\delta^{2}\leq\epsilon\delta^{2}(d-1)=r^{2}=\frac{1}{16}.$
(2)

Given an instance $\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ of
$d$-dimensional geometric $\geq$-CSP, we add a set $\mathcal{U}$ of points in
$\mathbb{R}^{d}$ as described in Table 1 and Table 2. These set of points are
the input for the instance of the $|\mathcal{V}|$-Center problem.

(1) Corresponding to variables: If $\mathbf{a}\in\mathcal{V}$ then we add the
following set of points which are collectively called as
$\textsc{Border}[\mathbf{a}]$ • For each $i\in[d]$, the point
$B_{\\_}{\mathbf{a}}^{+i}$ which is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r(1-\epsilon)}\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. • For each $i\in[d]$, the point $B_{\\_}{\mathbf{a}}^{-i}$
which is located at
$\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\cdot{\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}r(1-\epsilon)}\ominus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. This set of points are referred to as _border_ points. (2)
Corresponding to unary constraints: If $\mathbf{a}\in\mathcal{V}$ and
$\big{\langle}(\mathbf{a}),R_{\\_}{\mathbf{a}}\big{\rangle}$ is the unary
constraint on $\mathbf{a}$, then we add the following set of points which are
collectively called as $\textsc{Core}[\mathbf{a}]$: • for each $\mathbf{x}\in
R_{\\_}{\mathbf{a}}\subseteq[\delta]^{d}$ we add a point called
$C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ located at
$\mathbf{a}\oplus\epsilon\cdot\mathbf{x}$. This set of points are referred to
as _core_ points. (3) Corresponding to adjacencies in $G_{\\_}{\mathcal{I}}$:
For every edge $(\mathbf{a},\mathbf{a^{\prime}})$ in $G_{\\_}{\mathcal{I}}$ we
add a collection of $\delta$ points denoted by
$\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}$. Assume, without
loss of generality, that
$\mathbf{a^{\prime}}=\mathbf{a}\oplus\mathbf{e}_{\\_}i$ for some $i\in[d]$.
Then the set of points
$\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}$ is defined as
follows: • for each $\ell\in[\delta]$ we add a point
$S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}$ which is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot\left((1-\epsilon)2r+\epsilon\ell\right)$.
This set of points are referred to as _secondary_ points.

Table 1: The set $\mathcal{U}$ of points in $\mathbb{R}^{d}$ (which gives an
instance of $k$-Center ) constructed from an instance
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ of $d$-dimensional
geometric $\geq$-CSP.

Note that we add at most $|\mathcal{V}|\cdot 2d$ many border points, at most
$|\mathcal{C}|$ many core points, and at most $|\mathcal{V}|^{2}\cdot\delta$
many secondary points. Hence, the total number of points $n$ in the instance
$\mathcal{U}$ is $\leq|\mathcal{V}|\cdot
2d+|\mathcal{C}|+|\mathcal{V}|^{2}\cdot\delta=|\mathcal{I}|^{O(1)}$ where
$|\mathcal{I}|=|\mathcal{V}|+|\mathcal{D}|+|\mathcal{C}|$. We now prove some
preliminary lemmas to be later used in Section 2.3 and Section 2.4.

$\displaystyle\text{For each}\ \mathbf{a}\in\mathcal{V},\ \text{let}\
\mathcal{D}[\mathbf{a}]:=\textsc{Core}[\mathbf{a}]\ \bigcup\
\textsc{Border}[\mathbf{a}].$ (3) $\displaystyle\text{The set of primary
points is
{Primary}}:=\bigcup_{\\_}{\mathbf{a}\in\mathcal{V}}\mathcal{D}[\mathbf{a}].$
(4) $\displaystyle\text{The set of secondary points is
{Secondary}}:=\bigcup_{\\_}{\mathbf{a}\ \&\ \mathbf{a^{\prime}}\ \text{forms
an edge in}\
G_{\\_}\mathcal{I}}\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}.$
(5) $\displaystyle\text{The final collection of points is}\
\mathcal{U}:=\textsc{Primary}\ \bigcup\ \textsc{Secondary}.$ (6)

Table 2: Notation for some special subsets of points from $\mathcal{U}$. Note
that a primary point is either a core point or a border point.

####  2.2.1 Preliminary lemmas

######  Lemma .

For each $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$, we have
$\texttt{dist}\left(B_{\\_}{\mathbf{a}}^{+i},B_{\\_}{\mathbf{a}}^{-i}\right)\geq
2r(1+\epsilon)$.

###### Proof.

Fix any $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$. By Table 1, the points
$B_{\\_}{\mathbf{a}}^{+i}$ and $B_{\\_}{\mathbf{a}}^{-i}$ are located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$
and $\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\cdot
r(1-\epsilon)\ominus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$
respectively. Hence, we have that

$\displaystyle\texttt{dist}\left(B_{\\_}{\mathbf{a}}^{+i},B_{\\_}{\mathbf{a}}^{-i}\right)^{2}$
$\displaystyle=(2r(1-\epsilon))^{2}+(d-1)\cdot(4\epsilon\delta)^{2}=(2r(1-\epsilon))^{2}+16\epsilon\cdot(d-1)\epsilon\delta^{2},$
$\displaystyle=(2r(1-\epsilon))^{2}+16\epsilon\cdot r^{2},$ (by definition of
$\epsilon$ in Equation 1)
$\displaystyle=(2r)^{2}[(1-\epsilon)^{2}+4\epsilon]=(2r(1+\epsilon))^{2}.$

∎

######  Lemma .

For each $\mathbf{a}\in\mathcal{V}$, the distance between any two points in
$\textsc{Core}[\mathbf{a}]$ is $<r$.

###### Proof.

Fix any $\mathbf{a}\in\mathcal{V}$. Consider any two points in
$\textsc{Core}[\mathbf{a}]$, say $C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ and
$C_{\\_}{\mathbf{a}}^{\mathbf{y}}$, for some $\mathbf{x}\neq\mathbf{y}$. By
Table 1, these points are located at $\mathbf{a}\oplus\epsilon\cdot\mathbf{x}$
and $\mathbf{a}\oplus\epsilon\cdot\mathbf{y}$ respectively. Hence, we have

$\displaystyle\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},C_{\\_}{\mathbf{a}}^{\mathbf{y}}\right)^{2}$
$\displaystyle=\left(\epsilon\cdot\texttt{dist}(\mathbf{x},\mathbf{y})\right)^{2},$
$\displaystyle\leq\epsilon^{2}\cdot d\cdot(\delta-1)^{2},$ (since
$\mathbf{x},\mathbf{y}\in R_{\\_}{\mathbf{a}}\subseteq[\delta]^{d}$)
$\displaystyle=\frac{d(\delta-1)^{2}}{(d-1)^{2}\delta^{4}}\cdot r^{4},$ (by
definition of $\epsilon$ in Equation 1) $\displaystyle\leq\frac{1}{8}\cdot
r^{4}<r.$ (since $d\geq 2$ and $\delta\geq 1$)

∎

######  Lemma .

For each $\mathbf{a}\in\mathcal{V}$, the distance of any point from
$\textsc{Core}[\mathbf{a}]$ to any point from $\textsc{Border}[\mathbf{a}]$ is
$<2r$.

###### Proof.

Fix any $\mathbf{a}\in\mathcal{V}$ and consider any point
$C_{\\_}{\mathbf{a}}^{\mathbf{x}}\in\textsc{Core}[\mathbf{a}]$ where
$\mathbf{x}\in R_{\\_}{\mathbf{a}}\subseteq[\delta]^{d}$. We prove this lemma
by showing that, for each $i\in[d]$, the point
$C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ is at distance $<2r$ from both the points
$B_{\\_}{\mathbf{a}}^{+i}$ and $B_{\\_}{\mathbf{a}}^{-i}$. Fix some $i\in[d]$.

  1. (i)

By Table 1, the points $C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ and
$B_{\\_}{\mathbf{a}}^{+i}$ are located at
$\mathbf{a}\oplus\epsilon\cdot\mathbf{x}$ and
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$
respectively. Hence, we have

$\displaystyle\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},B_{\\_}{\mathbf{a}}^{+i}\right)^{2}$
$\displaystyle=(r(1-\epsilon)-\epsilon\cdot\mathbf{x}[i])^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(2\epsilon\delta-\epsilon\cdot\mathbf{x}[j])^{2},$
$\displaystyle\leq(r(1-\epsilon))^{2}+(d-1)(2\epsilon\delta)^{2},$ (since
$\mathbf{x}[i],\mathbf{x}[j]\geq 1$)
$\displaystyle=(r(1-\epsilon))^{2}+4\epsilon r^{2},$ (by definition of
$\epsilon$ in Equation 1) $\displaystyle=(r(1+\epsilon))^{2}<(2r)^{2}.$ (since
$\epsilon<1$)

  2. (ii)

By Table 1, the points $C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ and
$B_{\\_}{\mathbf{a}}^{-i}$ are located at
$\mathbf{a}\oplus\epsilon\cdot\mathbf{x}$ and
$\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\cdot
r(1-\epsilon)\ominus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$
respectively. Hence, we have

$\displaystyle\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},B_{\\_}{\mathbf{a}}^{-i}\right)^{2}$
$\displaystyle=(r(1-\epsilon)+\epsilon\cdot\mathbf{x}[i])^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(\epsilon\cdot\mathbf{x}[j]+2\epsilon\delta)^{2},$
$\displaystyle\leq(r(1-\epsilon)+\epsilon\delta)^{2}+(d-1)(3\epsilon\delta)^{2},$
(since $\mathbf{x}[i],\mathbf{x}[j]\leq\delta$)
$\displaystyle=(r(1-\epsilon)+\epsilon\delta)^{2}+9\epsilon r^{2},$ (by
definition of $\epsilon$) $\displaystyle\leq
2r^{2}(1-\epsilon)^{2}+2\epsilon^{2}\delta^{2}+9\epsilon r^{2},$ (since
$(\alpha+\beta)^{2}\leq 2\alpha^{2}+2\beta^{2}$) $\displaystyle\leq
2r^{2}(1-\epsilon)^{2}+11\epsilon r^{2},$ (since $\epsilon\delta^{2}\leq
r^{2}$)
$\displaystyle=2r^{2}((1-\epsilon)^{2}+5.5\epsilon)<2r^{2}(1+1.75\epsilon)^{2}<(2r)^{2}.$
(since $\epsilon\leq 1/16$)

∎

######  Claim .

For each $\mathbf{a}\in\mathcal{V}$, the distance of $\mathbf{a}$ to any point
in $\textsc{Border}[\mathbf{a}]$ is $r(1+\epsilon)$.

###### Proof.

Let $p$ be any point in $\textsc{Border}[\mathbf{a}]$. Then we have two
choices for $p$, namely $p=B_{\\_}{\mathbf{a}}^{+i}$ or
$p=B_{\\_}{\mathbf{a}}^{-i}$. In both cases, we have

$\displaystyle\texttt{dist}(p,\mathbf{a})^{2}=(r(1-\epsilon))^{2}+(d-1)(2\epsilon\delta)^{2}=r^{2}(1-\epsilon)^{2}+4\epsilon
r^{2}=(r(1+\epsilon))^{2},$

where the second equality is obtained by the definition of $\epsilon$
(Equation 1). ∎

######  Lemma .

For each $\mathbf{a}\in\mathcal{V}$ and each $i\in[d]$,

  * •

If $w\in\mathcal{U}$ such that
$\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{+i}\right)<2r(1+\epsilon)$ then
$w\in\left(\mathcal{D}[\mathbf{a}]\ \bigcup\
\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\\}}\right)$.

  * •

If $w\in\mathcal{U}$ such that
$\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{-i}\right)<2r(1+\epsilon)$ then
$w\in\left(\mathcal{D}[\mathbf{a}]\ \bigcup\
\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\\}}\right)$.

###### Proof.

The proof of this lemma is quite long, and is hence deferred to Appendix A to
maintain the flow of the paper. ∎

######  Remark .

Section 2.2.1 gives a necessary but not sufficient condition. Also, it might
be the case that for some $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$ the vector
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\notin\mathcal{V}\left(\mbox{resp.,
}\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\notin\mathcal{V}\right)$ in which case
the set
$\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\\}}\left(\mbox{resp.,
}\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\\}}\right)$
is empty.

######  Lemma .

Let $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$ be such that
$\mathbf{a}^{\prime}:=(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\in\mathcal{V}$. For
each $\ell\in[\delta]$,

  * (1)

If $\mathbf{x}\in R_{\\_}{\mathbf{a}}$ and $\ell\leq\mathbf{x}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)<2r$.

  * (2)

If $\mathbf{x}\in R_{\\_}{\mathbf{a}}$ and $\ell>\mathbf{x}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)\geq
2r(1+\epsilon)$.

  * (3)

If $\mathbf{y}\in R_{\\_}{\mathbf{a}^{\prime}}$ and $\ell>\mathbf{y}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{y}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)<2r$.

  * (4)

If $\mathbf{y}\in R_{\\_}{\mathbf{a}^{\prime}}$ and $\ell\leq\mathbf{y}[i]$,
then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{y}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)\geq
2r(1+\epsilon)$.

###### Proof.

Recall from Table 1 that the points $C_{\\_}{\mathbf{a}}^{\mathbf{x}}$ and
$S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}$ are located at
$\mathbf{a}\oplus\epsilon\cdot\mathbf{x}$ and
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot((1-\epsilon)2r+\epsilon\ell)$
respectively.

  * (1)

If $\ell\leq\mathbf{x}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)^{2}$

$\displaystyle=(2r(1-\epsilon)+\epsilon(\ell-\mathbf{x}[i]))^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(\epsilon\cdot\mathbf{x}[j])^{2},$
$\displaystyle\leq(2r(1-\epsilon))^{2}+(d-1)\epsilon^{2}\delta^{2}=(2r(1-\epsilon))^{2}+\epsilon
r^{2}$ (since $\ell\leq\mathbf{x}[i]$ and $\mathbf{x}[j]\leq\delta$)
$\displaystyle=(2r)^{2}\left((1-\epsilon)^{2}+\frac{\epsilon}{4}\right)<(2r)^{2}.$
(since $0<\epsilon<1$)

  * (2)

If $\ell>\mathbf{x}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}}^{\mathbf{x}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)^{2}$

$\displaystyle=(2r(1-\epsilon)+\epsilon(\ell-\mathbf{x}[i]))^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(\epsilon\cdot\mathbf{x}[j])^{2},$
$\displaystyle\geq(2r(1-\epsilon)+\epsilon)^{2}=(2r(1-\epsilon)+4r\epsilon)^{2}=(2r(1+\epsilon))^{2}.$
(since $\ell>\mathbf{x}[i]$ and $4r=1$)

We now show the remaining two claims: recall from Table 1 that the points
$C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{y}}$ and
$S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}$ are located at
$(\mathbf{a}^{\prime}\oplus\epsilon\cdot\mathbf{y})=\mathbf{a}\oplus\mathbf{e}_{\\_}i\oplus\epsilon\cdot\mathbf{y}$
and $\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot((1-\epsilon)2r+\epsilon\ell)$
respectively.

  * (3)

If $\ell>\mathbf{y}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{y}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)^{2}$

$\displaystyle=(1+\epsilon\cdot\mathbf{y}[i]-(1-\epsilon)2r-\epsilon\ell)^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(\epsilon\cdot\mathbf{y}[j])^{2},$
$\displaystyle\leq(4r+\epsilon\cdot\mathbf{y}[i]-(1-\epsilon)2r-\epsilon\ell)^{2}+(d-1)\epsilon^{2}\delta^{2},$
(since $4r=1$ and $\mathbf{y}[j]\leq\delta$)
$\displaystyle=(2r(1+\epsilon)-\epsilon(\ell-\mathbf{y}[i]))^{2}+\epsilon
r^{2},$ (since $(d-1)\epsilon\delta^{2}=r^{2}$)
$\displaystyle\leq(2r(1+\epsilon)-\epsilon)^{2}+\epsilon r^{2},$ (since
$\ell>\mathbf{y}[i]$) $\displaystyle=(2r(1-\epsilon))^{2}+\epsilon r^{2},$
(since $4r=1$)
$\displaystyle=(2r)^{2}\left((1-\epsilon)^{2}+\frac{\epsilon}{4}\right)<(2r)^{2}.$
(since $0<\epsilon<1$)

  * (4)

If $\ell\leq\mathbf{y}[i]$, then
$\texttt{dist}\left(C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{y}},S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\ell}\right)^{2}$

$\displaystyle=(1+\epsilon\cdot\mathbf{y}[i]-(1-\epsilon)2r-\epsilon\ell)^{2}+\sum_{\\_}{j=1\colon
j\neq i}^{d}(\epsilon\cdot\mathbf{y}[j])^{2},$
$\displaystyle\geq(2r(1+\epsilon)+\epsilon(\mathbf{y}[i]-\ell))^{2},$ (since
$4r=1$) $\displaystyle\geq(2r(1+\epsilon))^{2}.$ (since
$\mathbf{y}[i]\geq\ell$)

∎

######  Lemma .

Let $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$ be such that
$\mathbf{a}^{\prime}:=(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\in\mathcal{V}$. If
$\mathbf{a}^{\prime\prime}\notin\\{\mathbf{a},\mathbf{a}^{\prime}\\}$ then the
distance between any point in $\textsc{Core}[\mathbf{a}^{\prime\prime}]$ and
any point in $\mathcal{S}_{\\_}{\mathbf{a},\mathbf{a}^{\prime}}$ is at least
$2r(1+\epsilon)$.

###### Proof.

Let $\mathbf{p}$ and $\mathbf{q}$ be two arbitrary points from
$\textsc{Core}[\mathbf{a}^{\prime\prime}]$ and
$\mathcal{S}_{\\_}{\mathbf{a},\mathbf{a}^{\prime}}$, respectively. By Table 1,
$\mathbf{p}$ is located at
$\mathbf{a}^{\prime\prime}\oplus\epsilon\cdot\mathbf{x}$ for some
$\mathbf{x}\in R_{\\_}{\mathbf{a}}\subseteq[\delta]^{d}$ and $\mathbf{q}$ is
located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}i\cdot((1-\epsilon)2r+\epsilon\ell)$ for some
$\ell\in[\delta]$.

Since $\mathbf{a}^{\prime}=\mathbf{a}\oplus\mathbf{e}_{\\_}i$ and
$\mathbf{a}^{\prime\prime}\notin\\{\mathbf{a},\mathbf{a}^{\prime}\\}$, we have
three cases to consider:

  * •

$\mathbf{a}^{\prime\prime}[j]=\mathbf{a}[j]$ for all $j\neq i$ and
$\mathbf{a}^{\prime\prime}[i]\leq\mathbf{a}[i]-1$: In this case, we have
$\texttt{dist}(\mathbf{p},\mathbf{q})^{2}$

$\displaystyle\geq\left(\left(\mathbf{a}[i]+(1-\epsilon)2r+\epsilon\ell\right)-\left(\mathbf{a}^{\prime\prime}[i]+\epsilon\cdot\mathbf{x}[i]\right)\right)^{2},$
(only considering the $i$-th coordinate)
$\displaystyle=\left(\mathbf{a}[i]-\mathbf{a}^{\prime\prime}[i]+(1-\epsilon)2r+\epsilon\ell-\epsilon\mathbf{x}[i]\right)^{2},$
$\displaystyle\geq\left(1+(1-\epsilon)2r+\epsilon\cdot
4r-\epsilon\delta\right)^{2},$ (since
$\mathbf{a}[i]-\mathbf{a}^{\prime\prime}[i]\geq 1$, $\ell\geq 1=4r$ and
$\mathbf{x}[i]\leq\delta$) $\displaystyle>(2r(1+\epsilon))^{2}.$ (since
$1-\epsilon\delta\geq 1-\frac{1}{16}>0$)

  * •

$\mathbf{a}^{\prime\prime}[j]=\mathbf{a}[j]$ for all $j\neq i$ and
$\mathbf{a}^{\prime\prime}[i]\geq\mathbf{a}[i]+2$: In this case, we have
$\texttt{dist}(\mathbf{p},\mathbf{q})^{2}$

$\displaystyle\geq\left(\left(\mathbf{a}^{\prime\prime}[i]+\epsilon\cdot\mathbf{x}[i]\right)-\left(\mathbf{a}[i]+(1-\epsilon)2r+\epsilon\ell\right)\right)^{2},$
(only considering the $i$-th coordinate)
$\displaystyle=\left(\mathbf{a}^{\prime\prime}[i]-\mathbf{a}[i]-(1-\epsilon)2r+\epsilon\cdot\mathbf{x}[i]-\epsilon\ell\right)^{2},$
$\displaystyle\geq(2-(1-\epsilon)2r+\epsilon-\epsilon\delta)^{2},$ (since
$\mathbf{a}^{\prime\prime}[i]-\mathbf{a}[i]\geq 2$, $\mathbf{x}[i]\geq 1$ and
$\ell\leq\delta$)
$\displaystyle=(4r-(1-\epsilon)2r+1+\epsilon-\epsilon\delta)^{2},$ (since
$4r=1$) $\displaystyle>(2r(1+\epsilon))^{2}.$ (since $1-\epsilon\delta\geq
1-\frac{1}{16}>0$)

  * •

There exists $j\neq i$ such that
$\mathbf{a}^{\prime\prime}[j]\neq\mathbf{a}[j]$: In this case, we have
$\texttt{dist}(\mathbf{p},\mathbf{q})$

$\displaystyle\geq\left|\mathbf{a}[j]-\left(\mathbf{a}^{\prime\prime}[j]+\epsilon\cdot\mathbf{x}[j]\right)\right|,$
(only considering the $j$-th coordinate)
$\displaystyle\geq\left|\mathbf{a}[j]-\mathbf{a}^{\prime\prime}[j]\right|-\epsilon\cdot\mathbf{x}[j],$
(by triangle inequality) $\displaystyle\geq 1-\epsilon\cdot\delta,$ (since
$\mathbf{a}[j]\neq\mathbf{a}^{\prime\prime}[j]$ and $\mathbf{x}[j]\leq\delta$)
$\displaystyle\geq 2r+2r-r^{2}=2r+2r\left(1-\frac{r}{2}\right),$ (since $4r=1$
and $\epsilon\delta\leq r^{2}$) $\displaystyle>2r(1+\epsilon).$ (since
$1-\frac{r}{2}>\frac{1}{16}\geq\epsilon$)

∎

###  2.3 $\mathcal{I}$ has a satisfying assignment $\Rightarrow$ OPT for the
instance $\mathcal{U}$ of $|\mathcal{V}|$-Center is $<2r$

Suppose that the $d$-dimensional geometric $\geq$-CSP
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ has a satisfying
assignment $f:\mathcal{V}\to\mathcal{D}$. Consider the set of points $F$ given
by
$\Big{\\{}C_{\\_}{\mathbf{a}}^{f(\mathbf{a})}:\mathbf{a}\in\mathcal{V}\Big{\\}}$.
Since $f:\mathcal{V}\to\mathcal{D}$ is a satisfying assignment for
$\mathcal{I}$, it follows that $f(\mathbf{a})\in R_{\\_}{\mathbf{a}}$ for each
$\mathbf{a}\in\mathcal{V}$ and hence the set $F$ is well-defined. Clearly,
$|F|=|\mathcal{V}|$. We now show that

$\text{OPT}(F):=\Big{(}\max_{\\_}{u\in\mathcal{U}}\big{(}\min_{\\_}{v\in
F}\texttt{dist}(u,v)\big{)}\Big{)}<2r$

This implies that OPT for the instance $\mathcal{U}$ of $|\mathcal{V}|$-Center
is $<2r$. We show $\text{OPT}(F)<2r$ by showing that $\texttt{dist}(p,F)<2r$
for each $p\in\mathcal{U}$. From Table 1 and Table 2, it is sufficient to
consider the two cases depending on whether $p$ is a primary point or a
secondary point.

######  Lemma .

If $p$ is a primary point, then $\texttt{dist}(p,F)<2r$.

###### Proof.

If $p$ is a primary point, then by Table 1 and Table 2 it follows that $p$ is
either a core point or a border point:

  * •

$p$ is a core point: By Table 1, $p\in\textsc{Core}[\mathbf{b}]$ for some
$\mathbf{b}\in\mathcal{V}$. Then, Section 2.2.1 implies that
$\texttt{dist}\big{(}p,C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\big{)}<r$. Since
$C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\in F$, we have
$\texttt{dist}\big{(}p,F\big{)}\leq\texttt{dist}\big{(}p,C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\big{)}<r$.

  * •

$p$ is a border point: By Table 1, $p\in\textsc{Border}[\mathbf{b}]$ for some
$\mathbf{b}\in\mathcal{V}$. Then, Section 2.2.1 implies that
$\texttt{dist}\big{(}p,C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\big{)}<2r$. Since
$C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\in F$, we have
$\texttt{dist}\big{(}p,F\big{)}\leq\texttt{dist}\big{(}p,C_{\\_}{\mathbf{b}}^{f(\mathbf{b})}\big{)}<2r$.
∎

######  Lemma .

If $p$ is a secondary point, then $\texttt{dist}(p,F)<2r$.

###### Proof.

If $p$ is a secondary point, then by Table 1 and Table 2 it follows that there
exists $\mathbf{a}\in\mathcal{V},i\in[d]$ and $\ell\in[\delta]$ such that
$p=S_{\\_}{\\{\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}i\\}}^{\ell}$. Note
that $C_{\\_}{\mathbf{a}}^{f(\mathbf{a})}\in F$ and
$C_{\\_}{\mathbf{a}\oplus\mathbf{e}_{\\_}i}^{f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)}\in
F$. We now prove the lemma by showing that
$\min\Big{\\{}\texttt{dist}\big{(}p,C_{\\_}{\mathbf{a}}^{f(\mathbf{a})}\big{)};\texttt{dist}\big{(}p,C_{\\_}{\mathbf{a}\oplus\mathbf{e}_{\\_}i}^{f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)}\big{)}\Big{\\}}<2r$.
Since $f:\mathcal{V}\to\mathcal{D}$ is a satisfying assignment, the binary
constraint on $\mathbf{a}$ and $\mathbf{a}\oplus\mathbf{e}_{\\_}i$ is
satisfied, i.e., $\delta\geq f(\mathbf{a})[i]\geq
f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)[i]\geq 1$. Since $\ell\in[\delta]$ this
implies that either $\ell\leq f(\mathbf{a})[i]$ or
$\ell>f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)[i]$. The following implications
complete the proof:

  * •

If $\ell\leq f(\mathbf{a})[i]$, then Section 2.2.1(1) implies that
$\texttt{dist}\big{(}C_{\\_}{\mathbf{a}}^{f(\mathbf{a})},p\big{)}<2r$.

  * •

If $\ell>f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)[i]$, then Section 2.2.1(3)
implies that
$\texttt{dist}\big{(}C_{\\_}{\mathbf{a}\oplus\mathbf{e}_{\\_}i}^{f(\mathbf{a}\oplus\mathbf{e}_{\\_}i)},p\big{)}<2r$.
∎

From Table 2, Section 2.3 and Section 2.3 it follows that OPT for the instance
$\mathcal{U}$ of $|\mathcal{V}|$-Center is $<2r$.

###  2.4 $\mathcal{I}$ does not have a satisfying assignment $\Rightarrow$ OPT
for the instance $\mathcal{U}$ of $|\mathcal{V}|$-Center is $\geq
2r(1+\epsilon)$

Suppose that the instance $\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$
of $d$-dimensional geometric $\geq$-CSP does not have a satisfying assignment.
We want to now show that OPT for the instance $\mathcal{U}$ of
$|\mathcal{V}|$-Center is $\geq 2r(1+\epsilon)$. Fix any set
$Q\subseteq\mathcal{U}$ of size $|\mathcal{V}|$: it is sufficient to show that

$\text{OPT}(Q):=\Big{(}\max_{\\_}{u\in\mathcal{U}}\big{(}\min_{\\_}{v\in
Q}\texttt{dist}(u,v)\big{)}\Big{)}\geq 2r(1+\epsilon)$ (7)

We consider two cases: either $\big{|}Q\cap\textsc{Core}[\mathbf{a}]\big{|}=1$
for each $\mathbf{a}\in\mathcal{V}$ (Section 2.4) or not (Section 2.4).

######  Lemma .

If $\big{|}Q\cap\textsc{Core}[\mathbf{a}]\big{|}=1$ for each
$\mathbf{a}\in\mathcal{V}$ then $\text{OPT}(Q)\geq 2r(1+\epsilon)$.

###### Proof.

Since $|Q|=|\mathcal{V}|$ and $|Q\cap\textsc{Core}[\mathbf{a}]|=1$ for each
$\mathbf{a}\in\mathcal{V}$ it follows that the only points in $Q$ are core
points (see Table 1 for definition) and moreover $Q$ contains exactly one core
point corresponding to each element from $\mathcal{V}$. Let
$\phi:\mathcal{V}\to[\delta]^{d}$ be the function such that
$Q\cap\textsc{Core}[\mathbf{a}]=C_{\\_}{\mathbf{a}}^{\phi(\mathbf{a})}$. By
Table 1, it follows that $\phi(a)\in\textup{R}_{\\_}{\mathbf{a}}$ for each
$\mathbf{a}\in\mathcal{V}$.

Recall that we are assuming in this section that the instance
$\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ of $d$-dimensional
geometric $\geq$-CSP does not have a satisfying assignment. Hence, in
particular, the function $\phi:\mathcal{V}\to[\delta]^{d}$ is not a satisfying
assignment for $\mathcal{I}$. All unary constraints are satisfied since
$\phi(a)\in\textup{R}_{\\_}{\mathbf{a}}$ for each $\mathbf{a}\in\mathcal{V}$.
Hence, there is some binary constraint which is not satisfied by $\phi$: let
this constraint be violated for the pair
$\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}i$ for some
$\mathbf{a}\in\mathcal{V}$ and $i\in[d]$. Let us denote
$\mathbf{a}\oplus\mathbf{e}_{\\_}i$ by $\mathbf{a}^{\prime}$. The violation of
the binary constraint on $\mathbf{a}$ and $\mathbf{a}\oplus\mathbf{e}_{\\_}i$
by $\phi$ implies that
$1\leq\phi(\mathbf{a})[i]<\phi(\mathbf{a}^{\prime})[i]\leq\delta$. We now show
that
$\texttt{dist}\big{(}Q,S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\phi(\mathbf{a}^{\prime})[i]}\big{)}\geq
2r(1+\epsilon)$ which, in turn, implies that $\text{OPT}(Q)\geq
2r(1+\epsilon)$. The following implications complete the proof:

  * •

Section 2.2.1(2) implies that
$\texttt{dist}\big{(}S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\phi(\mathbf{a}^{\prime})[i]},C_{\\_}{\mathbf{a}}^{\phi(\mathbf{a})}\big{)}\geq
2r(1+\epsilon)$.

  * •

Section 2.2.1(4) implies that
$\texttt{dist}\big{(}S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\phi(\mathbf{a}^{\prime})[i]},C_{\\_}{\mathbf{a}^{\prime}}^{\phi(\mathbf{a}^{\prime})}\big{)}\geq
2r(1+\epsilon)$.

  * •

Consider any point $s\in
Q\setminus\big{\\{}C_{\\_}{\mathbf{a}}^{\phi(\mathbf{a})},C_{\\_}{\mathbf{a}^{\prime}}^{\phi(\mathbf{a}^{\prime})}\big{\\}}$.
Then $s\in\textsc{Core}[\mathbf{a}^{\prime\prime}]$ for some
$\mathbf{a}^{\prime\prime}\notin\big{\\{}\mathbf{a},\mathbf{a}^{\prime}\big{\\}}$.
Section 2.2.1 implies
$\texttt{dist}\big{(}S_{\\_}{\\{\mathbf{a},\mathbf{a}^{\prime}\\}}^{\phi(\mathbf{a}^{\prime})[i]},s\big{)}\geq
2r(1+\epsilon)$. ∎

######  Lemma .

If there exists $\mathbf{a}\in\mathcal{V}$ such that
$\big{|}Q\cap\textsc{Core}[\mathbf{a}]\big{|}\neq 1$ then $\text{OPT}(Q)\geq
2r(1+\epsilon)$.

###### Proof.

Suppose that $\text{OPT}(Q)<2r(1+\epsilon)$. To prove the lemma, we will now
show that this implies $|Q\cap\textsc{Core}[\mathbf{a}]|=1$ for each
$\mathbf{a}\in\mathcal{V}$. This is done via the following two claims, namely
Section 2.4 and Section 2.4.

######  Claim .

$\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}=1$ for each
$\mathbf{a}\in\mathcal{V}$

###### Proof.

Define three sets $I_{\\_}0,I_{\\_}1$ and $I_{\\_}{\geq 2}$ as follows:

$\displaystyle
I_{\\_}0:=\big{\\{}\mathbf{a}\in\mathcal{V}:\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}=0\big{\\}}$
(8) $\displaystyle
I_{\\_}1:=\big{\\{}\mathbf{a}\in\mathcal{V}:\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}=1\big{\\}}$
(9) $\displaystyle I_{\\_}{\geq
2}:=\big{\\{}\mathbf{a}\in\mathcal{V}:\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}\geq
2\big{\\}}$ (10)

By definition, we have

$|I_{\\_}0|+|I_{\\_}1|+|I_{\\_}{\geq 2}|=|\mathcal{V}|$ (11)

Consider a variable $\mathbf{b}\in I_{\\_}0$. Since
$\texttt{dist}\left(Q,B_{\\_}{\mathbf{b}}^{+i}\right)$ and
$\texttt{dist}\left(Q,B_{\\_}{\mathbf{b}}^{-i}\right)<2r(1+\epsilon)$, and
$Q\cap\mathcal{D}[\mathbf{b}]=\emptyset$, Section 2.2.1 implies that for each
$i\in[d]$

  1. (i)

$Q$ must contain a point from
$\mathcal{S}_{\\_}{\\{\mathbf{b},\mathbf{b}\oplus\mathbf{e}_{\\_}i\\}}$ since
$Q\cap\mathcal{D}[\mathbf{b}]=\emptyset$, and

  2. (ii)

$Q$ must contain a point from
$\mathcal{S}_{\\_}{\\{\mathbf{b},\mathbf{b}\ominus\mathbf{e}_{\\_}i\\}}$ since
$Q\cap\mathcal{D}[\mathbf{b}]=\emptyset$

Since each secondary point can be _“charged”_ to two variables in
$\mathcal{V}$ (recall the definition of secondary points from Table 1: each
secondary point is indexed by a set of two variables
$\\{\mathbf{b},\mathbf{b}^{\prime}\\}$ such that
$\mathbf{b}^{\prime}=\mathbf{b}\oplus\mathbf{e}_{\\_}i$ for some $i\in[d]$),
it follows that $Q$ contains $\geq\frac{2d}{2}=d\geq 2$ _distinct_ secondary
points corresponding to each variable in $I_{\\_}{0}$. Therefore, we have

$\displaystyle|I_{\\_}0|+|I_{\\_}1|+|I_{\\_}{\geq
2}|=\big{|}\mathcal{V}\big{|}$ (from Equation 11) $\displaystyle=|Q|$
$\displaystyle\geq|Q\cap\textsc{Primary}|+|Q\cap\textsc{Secondary}|$ (since
$\textsc{Primary}\cap\textsc{Secondary}=\emptyset$ )
$\displaystyle\geq\Big{(}|I_{\\_}1|+2|I_{\\_}{\geq
2}|\Big{)}+|Q\cap\textsc{Secondary}|$ (by definition of $I_{\\_}1$ and
$I_{\\_}{\geq 2}$) $\displaystyle\geq\Big{(}|I_{\\_}1|+2|I_{\\_}{\geq
2}|\Big{)}+2|I_{\\_}0|$ (12)

where the last inequality follows because $Q$ contains at least $2$ secondary
points corresponding to each variable in $I_{\\_}{0}$. Hence, we have
$|I_{\\_}0|+|I_{\\_}1|+|I_{\\_}{\geq 2}|\geq
2|I_{\\_}0|+|I_{\\_}1|+2|I_{\\_}{\geq 2}|$ which implies
$|I_{\\_}0|=0=|I_{\\_}{\geq 2}|$. From Equation 11, we get
$|I_{\\_}1|=\big{|}\mathcal{V}\big{|}$, i.e.,
$\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}=1$ for each
$\mathbf{a}\in\mathcal{V}$. This concludes the proof of Section 2.4. ∎

Since $|Q|=\big{|}\mathcal{V}\big{|}$ and
$\mathcal{D}[\mathbf{a}]\cap\mathcal{D}[\mathbf{b}]=\emptyset$ for distinct
$\mathbf{a},\mathbf{b}\in\mathcal{V}$, Section 2.4 implies that

$Q\ \text{contains no secondary points}$ (13)

We now prove that $Q$ doesn’t contain border points either.

######  Claim .

$\big{|}Q\cap\textsc{Core}[\mathbf{a}]\big{|}=1$ for each
$\mathbf{a}\in\mathcal{V}$

###### Proof.

Fix any $\mathbf{a}\in\mathcal{V}$. From Section 2.4, we know that
$\big{|}Q\cap\mathcal{D}[\mathbf{a}]\big{|}=1$. Suppose that this unique point
in $Q\cap\mathcal{D}[\mathbf{a}]$ is from $\textsc{Border}[\mathbf{a}]$.
Without loss of generality, let
$Q\cap\mathcal{D}[\mathbf{a}]=\big{\\{}B_{\\_}{\mathbf{a}}^{+i}\big{\\}}$ for
some $i\in[d]$. Since $\text{OPT}(Q)<2r(1+\epsilon)$, it follows that
$\texttt{dist}\big{(}Q,B_{\\_}{\mathbf{a}}^{-i}\big{)}<2r(1+\epsilon)$. Hence,
Section 2.2.1(2) implies that $Q\cap\Big{(}\mathcal{D}[\mathbf{a}]\ \bigcup\
\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\\}}\Big{)}\neq\emptyset$.
Since $Q$ contains no secondary points (Equation 13), we have
$Q\cap\left(\mathcal{D}[\mathbf{a}]\ \bigcup\
\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\ominus\mathbf{e}_{\\_}{i}\\}}\right)=Q\cap\mathcal{D}[\mathbf{a}]=\left\\{B_{\\_}{\mathbf{a}}^{+i}\right\\}$.
But from Section 2.2.1 we know
$\texttt{dist}\left(B_{\\_}{\mathbf{a}}^{+i},B_{\\_}{\mathbf{a}}^{-i}\right)\geq
2r(1+\epsilon)$. We thus obtain a contradiction. This concludes the proof of
Section 2.4. ∎

Therefore, we have shown that $\text{OPT}(Q)<2r(1+\epsilon)$ implies
$\big{|}Q\cap\textsc{Core}[\mathbf{a}]\big{|}=1$ for each
$\mathbf{a}\in\mathcal{V}$. This concludes the proof of Section 2.4. ∎

###  2.5 Finishing the proof of Theorem 1

Finally, we are ready to prove Theorem 1 which is restated below:

See 1

###### Proof.

Given an instance $\mathcal{I}=(\mathcal{V},\mathcal{D},\mathcal{C})$ of a
$d$-dimensional geometric $\geq$-CSP, we build an instance $\mathcal{U}$ of
$|\mathcal{V}|$-Center in $\mathbb{R}^{d}$ given by the reduction in Section
2.2. This reduction has the property that

  * •

if $\mathcal{I}$ has a satisfying assignment then OPT for the instance
$\mathcal{U}$ of $|\mathcal{V}|$-Center is $<2r$ (Section 2.3), and

  * •

if $\mathcal{I}$ does not have a satisfying assignment then OPT for the
instance $\mathcal{U}$ of $|\mathcal{V}|$-Center is $\geq 2r(1+\epsilon^{*})$
(Section 2.4)

where $r=1/4$ and
$\epsilon^{*}=\dfrac{r^{2}}{(d-1)\delta^{2}}\geq\dfrac{1}{16(d-1)|\mathcal{D}|}$,
since $|\mathcal{D}|=\left|[\delta]^{d}\right|\geq\delta^{2}$. Hence, any
algorithm for the $|\mathcal{V}|$-center problem which has an approximation
factor $\leq(1+\epsilon^{*})$ can solve the $d$-dimensional geometric
$\geq$-CSP. Note that the instance $\mathcal{U}$ of $k$-Center in
$\mathbb{R}^{d}$ has $k=|\mathcal{V}|$ and the number of points
$n\leq|\mathcal{V}|\cdot
2d+|\mathcal{C}|+|\mathcal{V}|^{2}\cdot\delta=|\mathcal{I}|^{O(1)}$ where
$|\mathcal{I}|=|\mathcal{V}|+|\mathcal{D}|+|\mathcal{C}|$. We now derive the
two lower bounds claimed in the theorem:

\- (Inapproximability result)

Suppose that there exists $d\geq 2$ such that the $k$-center on $n$ points in
$\mathbb{R}^{d}$ admits an $(1+\epsilon)$-approximation algorithm in
$f(k)\cdot\Big{(}\frac{1}{\epsilon}\Big{)}^{o(k^{1-1/d})}\cdot
n^{o(k^{1-1/d})}$ time for some computable function $f$. As argued above,
using a $(1+\epsilon^{*})$-approximation for the $k$-center problem with
$k=|\mathcal{V}|$ and $n=|\mathcal{I}|^{O(1)}$ points can solve the
$d$-dimensional geometric $\geq$-CSP problem. Recall that
$16(d-1)|\cdot\mathcal{I}|\geq
16(d-1)|\cdot\mathcal{D}|\geq\frac{1}{\epsilon^{*}}$ since
$|I|=|\mathcal{V}|+|\mathcal{D}|+|\mathcal{C}|$, and hence we have an
algorithm for the $d$-dimensional geometric $\geq$-CSP problem which runs in
time
$f(|\mathcal{V}|)\cdot(16d)^{o(k^{1-1/d})}\cdot|\mathcal{I}|^{o(k^{1-1/d})}$
which contradicts Theorem 2.

\- (Lower bound for exact algorithm)

Suppose that there exists $d\geq 2$ such that the $k$-center on $n$ points in
$\mathbb{R}^{d}$ admits an exact algorithm in $f(k)\cdot n^{o(k^{1-1/d})}$
time for some computable function $f$. As argued above777The argument above is
actually stronger: even a $(1+\epsilon^{*})$-approximation algorithm for
$k$-center can solve $d$-dimensional geometric $\geq$-CSP, solving the $k$
center problem with $k=|\mathcal{V}|$ and $n=|\mathcal{I}|^{O(1)}$ points can
solve the $d$-dimensional geometric $\geq$-CSP problem. Hence, we have an
algorithm for the $d$-dimensional geometric $\geq$-CSP problem which runs in
time $f(|\mathcal{V}|)\cdot|\mathcal{I}|^{o(k^{1-1/d})}$ which again
contradicts Theorem 2. ∎

## References

  * Aboulker et al. [2017] Pierre Aboulker, Nick Brettell, Frédéric Havet, Dániel Marx, and Nicolas Trotignon.  Coloring graphs with constraints on connectivity.  _Journal of Graph Theory_ , 85(4):814–838, 2017\.
  * Agarwal and Procopiuc [2002] Pankaj K. Agarwal and Cecilia Magdalena Procopiuc.  Exact and approximation algorithms for clustering.  _Algorithmica_ , 33(2):201–226, 2002.
  * Alber and Fiala [2004] Jochen Alber and Jirí Fiala.  Geometric separation and exact solutions for the parameterized independent set problem on disk graphs.  _J. Algorithms_ , 52(2):134–151, 2004.
  * [4] Amariah Becker, Philip N. Klein, and David Saulpic.  Polynomial-Time Approximation Schemes for k-center, k-median, and Capacitated Vehicle Routing in Bounded Highway Dimension.  In _ESA 2018_ , volume 112, pages 8:1–8:15.
  * Biró et al. [2018] Csaba Biró, Édouard Bonnet, Dániel Marx, Tillmann Miltzow, and Pawel Rzazewski.  Fine-grained complexity of coloring unit disks and balls.  _J. Comput. Geom._ , 9(2):47–80, 2018.
  * Cabello et al. [2011] Sergio Cabello, Panos Giannopoulos, Christian Knauer, Dániel Marx, and Günter Rote.  Geometric clustering: Fixed-parameter tractability and lower bounds with respect to the dimension.  _ACM Trans. Algorithms_ , 7(4):43:1–43:27, 2011\.
  * Chitnis et al. [2020] Rajesh Hemant Chitnis, Andreas Emil Feldmann, Mohammad Taghi Hajiaghayi, and Dániel Marx.  Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions).  _SIAM J. Comput._ , 49(2):318–364, 2020.
  * [8] Vincent Cohen-Addad, Arnaud de Mesmay, Eva Rotenberg, and Alan Roytman.  The Bane of Low-Dimensionality Clustering.  In _SODA 2018_ , pages 441–456.
  * Cygan et al. [2015] Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  _Parameterized Algorithms_.  Springer, 2015.  ISBN 978-3-319-21274-6.
  * [10] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, and Sudeshna Kolay.  An ETH-Tight Exact Algorithm for Euclidean TSP.  In _FOCS 2018_ , pages 450–461.
  * de Berg et al. [2020] Mark de Berg, Hans L. Bodlaender, Sándor Kisfaludi-Bak, Dániel Marx, and Tom C. van der Zanden.  A Framework for Exponential-Time-Hypothesis-Tight Algorithms and Lower Bounds in Geometric Intersection Graphs.  _SIAM J. Comput._ , 49(6):1291–1331, 2020.
  * Demaine et al. [2005a] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos.  Fixed-parameter algorithms for (_k_ , _r_)-center in planar graphs and map graphs.  _ACM Trans. Algorithms_ , 1(1):33–47, 2005a.
  * Demaine et al. [2005b] Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, and Dimitrios M. Thilikos.  Subexponential parameterized algorithms on bounded-genus graphs and _H_ -minor-free graphs.  _J. ACM_ , 52(6):866–893, 2005b.
  * Feldmann [2019] Andreas Emil Feldmann.  Fixed-parameter approximations for k-center problems in low highway dimension graphs.  _Algorithmica_ , 81(3):1031–1052, 2019.
  * Feldmann and Marx [2020] Andreas Emil Feldmann and Dániel Marx.  The parameterized hardness of the k-center problem in transportation networks.  _Algorithmica_ , 82(7):1989–2005, 2020.
  * Fomin et al. [a] Fedor V. Fomin, Sudeshna Kolay, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh.  Subexponential Algorithms for Rectilinear Steiner Tree and Arborescence Problems.  In _SoCG 2016_ , pages 39:1–39:15, a.
  * Fomin et al. [b] Fedor V. Fomin, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh.  Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering.  In _FOCS 2016_ , pages 515–524, b.
  * [18] Eli Fox-Epstein, Philip N. Klein, and Aaron Schild.  Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems.  In _SODA 2019_ , pages 1069–1088.
  * [19] Yogesh A. Girdhar and Gregory Dudek.  Efficient on-line data summarization using extremum summaries.  In _ICRA 2012_ , pages 3490–3496.
  * Gonzalez [1985] Teofilo F. Gonzalez.  Clustering to minimize the maximum intercluster distance.  _Theor. Comput. Sci._ , 38:293–306, 1985.
  * Hakimi [1971] S. Louis Hakimi.  Steiner’s problem in graphs and its implications.  _Networks_ , 1(2):113–133, 1971.
  * Hennig et al. [2015] Christian Hennig, Marina Meila, Fionn Murtagh, and Roberto Rocci.  _Handbook of cluster analysis_.  CRC Press, 2015.
  * Hochbaum and Shmoys [1985] Dorit S. Hochbaum and David B. Shmoys.  A best possible heuristic for the _k_ -center problem.  _Math. Oper. Res._ , 10(2):180–184, 1985.
  * Hsu and Nemhauser [1979] Wen-Lian Hsu and George L. Nemhauser.  Easy and hard bottleneck location problems.  _Discret. Appl. Math._ , 1(3):209–215, 1979.
  * Hwang et al. [1993a] R. Z. Hwang, R. C. Chang, and Richard C. T. Lee.  The Searching over Separators Strategy To Solve Some NP-Hard Problems in Subexponential Time.  _Algorithmica_ , 9(4):398–423, 1993a.
  * Hwang et al. [1993b] R. Z. Hwang, Richard C. T. Lee, and R. C. Chang.  The Slab Dividing Approach To Solve the Euclidean $p$-Center Problem.  _Algorithmica_ , 9(1):1–22, 1993b.
  * Impagliazzo and Paturi [2001] Russell Impagliazzo and Ramamohan Paturi.  On the Complexity of $k$-SAT.  _J. Comput. Syst. Sci._ , 62(2):367–375, 2001\.
  * Impagliazzo et al. [2001] Russell Impagliazzo, Ramamohan Paturi, and Francis Zane.  Which Problems Have Strongly Exponential Complexity?  _J. Comput. Syst. Sci._ , 63(4):512–530, 2001\.
  * Jiang et al. [2004] Daxin Jiang, Chun Tang, and Aidong Zhang.  Cluster analysis for gene expression data: a survey.  _IEEE Transactions on knowledge and data engineering_ , 16(11):1370–1386, 2004.
  * Katsikarelis et al. [2019] Ioannis Katsikarelis, Michael Lampis, and Vangelis Th. Paschos.  Structural parameters, tight bounds, and approximation for (k, r)-center.  _Discret. Appl. Math._ , 264:90–117, 2019.
  * Klein and Marx [a] Philip N. Klein and Dániel Marx.  Solving Planar $k$-Terminal Cut in O$(n^{c\sqrt{k}})$ Time.  In _ICALP 2012_ , pages 569–580, a.
  * Klein and Marx [b] Philip N. Klein and Dániel Marx.  A subexponential parameterized algorithm for Subset TSP on planar graphs.  In _SODA 2014_ , pages 1812–1830, b.
  * [33] Daniel Lokshtanov, Saket Saurabh, and Magnus Wahlström.  Subexponential Parameterized Odd Cycle Transversal on Planar Graphs.  In _FSTTCS 2012_ , pages 424–434.
  * Marx [a] Dániel Marx.  A Tight Lower Bound for Planar Multiway Cut with Fixed Number of Terminals.  In _ICALP 2012_ , pages 677–688, a.
  * Marx [b] Dániel Marx.  Parameterized complexity of independence and domination on geometric graphs.  In Hans L. Bodlaender and Michael A. Langston, editors, _IWPEC 2006_ , pages 154–165, b.
  * Marx [c] Dániel Marx.  Efficient Approximation Schemes for Geometric Problems?  In _ESA 2005_ , pages 448–459, c.
  * [37] Dániel Marx and Michal Pilipczuk.  Optimal Parameterized Algorithms for Planar Facility Location Problems Using Voronoi Diagrams.  In _ESA 2015_ , pages 865–877.
  * [38] Dániel Marx and Anastasios Sidiropoulos.  The limited blessing of low dimensionality: when $1-1/d$ is the best possible exponent for $d$-dimensional geometric problems.  In _SoCG 2014_ , page 67.
  * [39] Dániel Marx, Marcin Pilipczuk, and Michal Pilipczuk.  On Subexponential Parameterized Algorithms for Steiner Tree and Directed Subset TSP on Planar Graphs.  In _FOCS 2018_ , pages 474–484.
  * Moens et al. [1999] Marie-Francine Moens, Caroline Uyttendaele, and Jos Dumortier.  Abstracting of legal cases: The potential of clustering based on the selection of representative objects.  _J. Am. Soc. Inf. Sci._ , 50(2):151–161, 1999\.
  * [41] Marcin Pilipczuk, Michal Pilipczuk, Piotr Sankowski, and Erik Jan van Leeuwen.  Subexponential-Time Parameterized Algorithm for Steiner Tree on Planar Graphs.  In _STACS 2013_ , pages 353–364.
  * [42] Warren D. Smith and Nicholas C. Wormald.  Geometric separator theorems & applications.  In _FOCS 1998_ , pages 232–243.
  * Vazirani [2001] Vijay V. Vazirani.  _Approximation algorithms_.  Springer, 2001.  ISBN 978-3-540-65367-7.

##  Appendix A Proof of Section 2.2.1

###### Proof.

Fix some $\mathbf{a}\in\mathcal{V}$ and $i\in[d]$. To show the first part of
lemma, it suffices to show that if
$w\in\mathcal{U}\setminus\left(\mathcal{D}[\mathbf{a}]\ \bigcup\
\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\\}}\right)$
then $\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{+i}\right)\geq
2r(1+\epsilon)$. We argue based on whether $w$ is a primary or secondary
point. Recall,
$B_{\\_}{\mathbf{a}}^{+i}=\mathbf{a}\oplus\mathbf{e}_{\\_}i\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$.

We begin with the following two cases which arise when $w$ is a primary point.

  1. (1)

$w\in\textsc{Core}[\mathbf{a}^{\prime}]$ for some
$\mathbf{a}^{\prime}\neq\mathbf{a}$: From Table 1, we know
$w=C_{\\_}{\mathbf{a}^{\prime}}^{\mathbf{x}}$ for some $\mathbf{x}\in
R_{\\_}{\mathbf{a}^{\prime}}\subseteq[\delta]^{d}$. That is,
$w=\mathbf{a}^{\prime}\oplus\epsilon\cdot\mathbf{x}$. Since
$\mathbf{a}\neq\mathbf{a}^{\prime}$, it follows that $\mathbf{a}$ and
$\mathbf{a}^{\prime}$ differ in at least one coordinate, say the $j$-th
coordinate.

     * (i)

$i\neq j$: In this case, we have

$\displaystyle\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{+i}\right)$
$\displaystyle\geq\big{|}(\mathbf{a}^{\prime}[j]+\epsilon\cdot\mathbf{x}[j])-(\mathbf{a}[j]+2\epsilon\delta)\big{|},$
(only considering the $j$-th coordinate)
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[j]-\mathbf{a}[j]\big{|}-\big{|}2\epsilon\delta-\epsilon\cdot\mathbf{x}[j]\big{|},$
(by triangle inequality) $\displaystyle\geq 1-2\epsilon\delta,$ (since
$\mathbf{a}^{\prime}[j]\neq\mathbf{a}[j]$ and $\mathbf{x}[j]\in[\delta$])
$\displaystyle\geq 2r(1+\epsilon).$ (from Equation 1 and Equation 2)

     * (ii)

$i=j$: In this case, we have

$\displaystyle\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{+i}\right)$
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[i]+\epsilon\cdot\mathbf{x}[i]-\mathbf{a}[i]-r(1-\epsilon)\big{|},$
(only considering the $i$-th coordinate)
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[i]-\mathbf{a}[i]\big{|}-\big{|}r(1-\epsilon)-\epsilon\cdot\mathbf{x}[i]\big{|},$
(by triangle inequality) $\displaystyle\geq 4r-r(1-5\epsilon),$ (since
$\mathbf{a}^{\prime}[i]\neq\mathbf{a}[i]$, $4r=1$, and $\mathbf{x}[i]\geq 1$)
$\displaystyle\geq 2r(1+\epsilon).$ (from Equation 1 and Equation 2)

  2. (2)

$w\in\textsc{Border}[\mathbf{a}^{\prime}]$ for some
$\mathbf{a}^{\prime}\neq\mathbf{a}$: From Table 1,
$w\in\left\\{B_{\\_}{\mathbf{a}^{\prime}}^{+q},B_{\\_}{\mathbf{a}^{\prime}}^{-q}\right\\}$
for some $q\in[d]$. Since $\mathbf{a}\neq\mathbf{a}^{\prime}$, they differ in
at least one coordinate, say the $j$-th coordinate. We now consider two cases
depending on $\texttt{dist}\left(\mathbf{a},\mathbf{a}^{\prime}\right)$.

     * (i)

$\texttt{dist}\left(\mathbf{a},\mathbf{a}^{\prime}\right)\geq\sqrt{2}$: By the
triangle inequality we have 2≤dist(a,a’)≤dist(a, Ba^+i) + dist(Ba^+i, w) +
dist(w, a’).2≤dist(a,a’)≤dist(a, Ba^+i) + dist(Ba^+i, w) + dist(w, a’).
2≤dist(a,a’)≤dist(a, Ba^+i) + dist(Ba^+i, w) + dist(w, a’).&

$\sqrt{2}\leq\texttt{dist}\left(\mathbf{a},\mathbf{a}^{\prime}\right)\leq\texttt{dist}\left(\mathbf{a},B_{\\_}{\mathbf{a}}^{+i}\right)+\texttt{dist}\left(B_{\\_}{\mathbf{a}}^{+i},w\right)+\texttt{dist}\left(w,\mathbf{a}^{\prime}\right).$

By Section 2.2.1, it follows that
$\texttt{dist}\left(\mathbf{a},B_{\\_}{\mathbf{a}}^{+i}\right)=r(1+\epsilon)$
and $\texttt{dist}(w,\mathbf{a}^{\prime})=r(1+\epsilon)$ (since
$w\in\textsc{Border}[\mathbf{a}^{\prime}]$). Hence, we have
$\texttt{dist}(B_{\\_}{\mathbf{a}}^{+i},w)\geq\sqrt{2}-2r(1+\epsilon)=4\sqrt{2}r-2r(1+\epsilon)\geq
2r(1+\epsilon)$, where in the last bound we have used Equation 1 and Equation
2.

     * (ii)

$\texttt{dist}\left(\mathbf{a},\mathbf{a}^{\prime}\right)=1$: In this case, we
have
$\texttt{dist}\left(\mathbf{a},\mathbf{a}^{\prime}\right)=\big{|}\mathbf{a}[j]-\mathbf{a}^{\prime}[j]\big{|}=1$.
Recall
$w\in\left\\{B_{\\_}{\mathbf{a}^{\prime}}^{+q},B_{\\_}{\mathbf{a}^{\prime}}^{-q}\right\\}$,
where

$\displaystyle B_{\\_}{\mathbf{a}^{\prime}}^{+q}$
$\displaystyle=\mathbf{a}^{\prime}\oplus\mathbf{e}_{\\_}{q}\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}q)\cdot
2\epsilon\delta\quad\text{ and }$ $\displaystyle
B_{\\_}{\mathbf{a}^{\prime}}^{-q}$
$\displaystyle=\mathbf{a}^{\prime}\ominus\mathbf{e}_{\\_}{q}\cdot
r(1-\epsilon)\ominus(\mathbf{1}^{d}-\mathbf{e}_{\\_}q)\cdot 2\epsilon\delta.$

Further recall
$B_{\\_}{\mathbf{a}}^{+i}=\mathbf{a}\oplus\mathbf{e}_{\\_}i\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$.
There are four cases to consider:

       * –

$j\notin\\{i,q\\}$: In this case, we have

$\displaystyle\texttt{dist}\left(w,B_{\\_}{\mathbf{a}}^{+i}\right)$
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[j]-\mathbf{a}[j]-4\epsilon\delta\big{|},$
(only considering the $j$-th coordinate) $\displaystyle\geq
1-4\epsilon\delta,$ (by triangle inequality and
$\mathbf{a}[j]\neq\mathbf{a}^{\prime}[j]$) $\displaystyle\geq 2r(1+\epsilon).$
(from Equation 1 and Equation 2)

       * –

$j=i=q$: In this case, we have

$\displaystyle\texttt{dist}(w,B_{\\_}{\mathbf{a}}^{+i})$
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[j]-\mathbf{a}[j]-2r(1-\epsilon)\big{|},$
(only considering the $j$-th coordinate) $\displaystyle\geq
4r-2r(1-\epsilon),$ (by triangle inequality,
$\mathbf{a}[j]\neq\mathbf{a}^{\prime}[j]$, and $4r=1$) $\displaystyle\geq
2r(1+\epsilon).$

       * –

$j=i$ and $i\neq q$: In this case, we have

$\displaystyle\texttt{dist}(w,B_{\\_}{\mathbf{a}}^{+i})$
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[j]-\mathbf{a}[j]-r(1-\epsilon)-2\epsilon\delta\big{|},$
(only considering the $j$-th coordinate) $\displaystyle\geq
1-r(1-\epsilon)-2\epsilon\delta,$ (since
$\mathbf{a}[j]\neq\mathbf{a}^{\prime}[j]$) $\displaystyle\geq 2r(1+\epsilon).$
(from Equation 1 and Equation 2)

       * –

$j=q$ and $q\neq i$: In this case, we have

$\displaystyle\texttt{dist}(w,B_{\\_}{\mathbf{a}}^{+i})$
$\displaystyle\geq\big{|}\mathbf{a}^{\prime}[j]-\mathbf{a}[j]-r(1-\epsilon)-2\epsilon\delta\big{|},$
(only considering the $j$-th coordinate) $\displaystyle\geq 2r(1+\epsilon).$
(same as the previous case)

We now consider the following three cases which arise when $w$ is a secondary
point.

  1. (3)

$w\in\mathcal{S}_{\\_}{\\{\mathbf{a},\mathbf{a}^{*}\\}}$ for some
$\mathbf{a}^{*}\neq(\mathbf{a}\oplus\mathbf{e}_{\\_}i)$: Let
$w=S_{\\_}{\\{\mathbf{a},\mathbf{a}^{*}\\}}^{\ell}$ for some
$\ell\in[\delta]$. By definition of Secondary (see Table 2), the variables
$\mathbf{a}$ and $\mathbf{a}^{*}$ must form an edge in the constraint graph
$G_{\\_}{\mathcal{I}}$. Since $G_{\\_}{\mathcal{I}}$ is a subgraph of the
$d$-dimensional grid, it suffices to consider the following three cases:

    1. (i)

$\mathbf{a}^{*}=\mathbf{a}\ominus\mathbf{e}_{\\_}i$ : From Table 1, the point
$w=S_{\\_}{\\{\mathbf{a}^{*},\mathbf{a}\\}}^{\ell}$ is located at
$\mathbf{a}^{*}\oplus\mathbf{e}_{\\_}{i}\cdot\left((1-\epsilon)2r+\epsilon\ell\right)=(\mathbf{a}\ominus\mathbf{e}_{\\_}i)\oplus\mathbf{e}_{\\_}{i}\cdot\left((1+\epsilon)2r+\epsilon\ell\right)$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot
r(1-\epsilon)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot 2\epsilon\delta$.
Therefore, the distance between $w$ and $B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\left|\left(r(1-\epsilon)+2r-\epsilon\cdot(\ell-2r)\right)\right|,$
(considering only the $i$-th coordinate and using $4r=1$)
$\displaystyle=\left|(2r(1+\epsilon)+r(1-\epsilon)-\epsilon\ell)\right|,$
$\displaystyle>2r(1+\epsilon).$ (from $\ell\leq\delta$, Equation 1 and
Equation 2)

    2. (ii)

$\mathbf{a}^{*}=\mathbf{a}\oplus\mathbf{e}_{\\_}j$ for some $j\neq i$ : From
Table 1, the point $w=S_{\\_}{\\{\mathbf{a}^{*},\mathbf{a}\\}}^{\ell}$ is
located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Therefore, square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}2r+\epsilon\cdot(\ell-2r)-2\epsilon\delta\big{)}^{2}+(r-\epsilon/4)^{2}$
(ignoring all coordinates except $i$-th & $j$-th)
$\displaystyle\geq\big{(}2r-2\epsilon\delta\big{)}^{2}+(r-\epsilon/4)^{2}$
(from $\ell\geq 1$ and Equation 1)
$\displaystyle>\big{(}2r(1+\epsilon)\big{)}^{2}$ (from Equation 1 and Equation
2)

    3. (iii)

$\mathbf{a}^{*}=\mathbf{a}\ominus\mathbf{e}_{\\_}j$ for some $j\neq i$ : From
Table 1, the point $w=S_{\\_}{\\{\mathbf{a}^{*},\mathbf{a}\\}}^{\ell}$ is
located at
$\mathbf{a}^{*}\oplus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}=(\mathbf{a}\ominus\mathbf{e}_{\\_}j)\oplus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Therefore, square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}2\epsilon\delta+2r-\epsilon\cdot(\ell-2r)\big{)}^{2}+(r-\epsilon/4)^{2}$
(only considering coordinates $i$ and $j$)
$\displaystyle>(2r+\epsilon\cdot\delta)^{2}+(r-\epsilon/4)^{2}$ (from
$\ell\leq\delta$, Equation 1 and Equation 2)
$\displaystyle>\big{(}2r(1+\epsilon)\big{)}^{2}$ (from Equation 1 and Equation
2)

  2. (4)

$w\in\mathcal{S}_{\\_}{\\{\mathbf{a}\oplus\mathbf{e}_{\\_}i,\mathbf{a}^{**}\\}}$
for some $\mathbf{a}^{**}\neq\mathbf{a}$: Let
$w=S_{\\_}{\\{\mathbf{a}\oplus\mathbf{e}_{\\_}i,\mathbf{a}^{**}\\}}^{\ell}$
for some $\ell\in[\delta]$. By definition of Secondary (see Table 2), the
variables $\mathbf{a}\oplus\mathbf{e}_{\\_}i$ and $\mathbf{a}^{**}$ must form
an edge in the constraint graph $G_{\\_}{\mathcal{I}}$. Since
$G_{\\_}{\mathcal{I}}$ is a subgraph of the $d$-dimensional grid, it suffices
to consider the following three cases:

    1. (i)

$\mathbf{a}^{**}=(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\oplus\mathbf{e}_{\\_}i=\mathbf{a}\oplus
2\mathbf{e}_{\\_}i$ : From Table 1, the point
$w=S_{\\_}{\\{\mathbf{a}^{**},\mathbf{a}\oplus\mathbf{e}_{\\_}i\\}}^{\ell}$ is
located at
$(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\oplus\mathbf{e}_{\\_}{i}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Therefore, square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}1+2r+\epsilon\cdot(\ell-2r)-(r-\epsilon/4)\big{)}^{2}$
(ignoring all coordinates except $i$-th)
$\displaystyle>\big{(}1+2r-(r-\epsilon/4)\big{)}^{2}$ (since $\ell\geq 1>2r$)
$\displaystyle>\big{(}2r(1+\epsilon)\big{)}^{2}$ (from Equation 1 and Equation
2)

    2. (ii)

$\mathbf{a}^{**}=(\mathbf{a}\oplus\mathbf{e}_{\\_}i)+\mathbf{e}_{\\_}j$ for
some $j\neq i$ : From Table 1, the point
$w=S_{\\_}{\\{\mathbf{a}^{**},\mathbf{a}\oplus\mathbf{e}_{\\_}i\\}}^{\ell}$ is
located at
$(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\oplus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Therefore, square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}1-(r-\epsilon/4)\big{)}^{2}$ (ignoring all
coordinates except $i$-th) $\displaystyle>\big{(}2r(1+\epsilon)\big{)}^{2}$
(from Equation 1 and Equation 2)

    3. (iii)

$\mathbf{a}^{**}=(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\ominus\mathbf{e}_{\\_}j$
for some $j\neq i$ : From Table 1, the point
$w=S_{\\_}{\\{\mathbf{a}^{**},\mathbf{a}\oplus\mathbf{e}_{\\_}i\\}}^{\ell}$ is
located at
$(\mathbf{a}\oplus\mathbf{e}_{\\_}i)\ominus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Therefore, square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}1-(r-\epsilon/4)\big{)}^{2}$ (ignoring all
coordinates except $i$-th) $\displaystyle>\big{(}2r(1+\epsilon)\big{)}^{2}$
(from Equation 1 and Equation 2)

  3. (5)

$w\in\mathcal{S}_{\\_}{\\{\mathbf{b},\mathbf{b}\oplus\mathbf{e}_{\\_}j\\}}$
for some $\mathbf{b}$ and index $j\in[d]$ such that
$\\{\mathbf{b},\mathbf{b}\oplus\mathbf{e}_{\\_}j\\}\cap\\{\mathbf{a},\mathbf{a}\oplus\mathbf{e}_{\\_}i\\}=\emptyset$:
From Table 1, the point
$w=S_{\\_}{\\{\mathbf{b},\mathbf{b}\oplus\mathbf{e}_{\\_}j\\}}^{\ell}$ is
located at
$\mathbf{b}\oplus\mathbf{e}_{\\_}{j}\cdot\big{(}2r+\epsilon\cdot(\ell-2r)\big{)}$
for some $\ell\in[\delta]$ and the point $B_{\\_}{\mathbf{a}}^{+i}$ is located
at
$\mathbf{a}\oplus\mathbf{e}_{\\_}{i}\cdot(r-\epsilon/4)\oplus(\mathbf{1}^{d}-\mathbf{e}_{\\_}i)\cdot
2\epsilon\delta$. Since $\mathbf{a}\neq\mathbf{b}$ there exists an index
$i^{\prime}\in[d]$ such that
$\mathbf{a}[i^{\prime}]\neq\mathbf{b}[i^{\prime}]$. We have the following four
cases:

    1. (i)

$i^{\prime}\notin\\{i,j\\}$ : By only considering the $i^{\prime}$-th
coordinate, it follows that square of the distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is $\geq 1>\big{(}2r(1+\epsilon)\big{)}^{2}$ since
$r=\frac{1}{4}$ (Equation 1) and $\epsilon\leq 1/16$ (Equation 2).

    2. (ii)

$i^{\prime}=i$ and $i^{\prime}\neq j$ : By only considering the $i$-th
coordinate, it follows that distance between $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{|}\mathbf{a}[i]+r-\epsilon/4-\mathbf{b}[i]\big{|}$
(only considering the $i^{\text{th}}$-coordinate)
$\displaystyle\geq\big{|}\mathbf{a}[i]-\mathbf{b}[i]\big{|}-\big{|}r-\epsilon/4\big{|}$
(by triangle inequality) $\displaystyle\geq 1-(r-\epsilon/4)$ (from Equation 1
and Equation 2) $\displaystyle\geq 2r(1+\epsilon)$ (from Equation 1 and
Equation 2)

    3. (iii)

$i^{\prime}=j$ and $i^{\prime}\neq i$ : The absolute value of difference
between $i$-th coordinates of $w$ and $B_{\\_}{\mathbf{a}}^{+i}$ is
$\big{|}(\mathbf{a}[i]+r-\epsilon/4)-\mathbf{b}[i]\big{|}\geq(r-\epsilon/4)$
since $r=\frac{1}{4}$ and $\mathbf{a}[i],\mathbf{b}[i]\in[\delta]$. The
absolute value of difference between $j$-th coordinates of $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is
$\big{|}\big{(}\mathbf{b}[j]+2r+\epsilon(\ell-2r)\big{)}-\big{(}\mathbf{a}[j]+2\epsilon\delta\big{)}\big{|}\geq\big{|}\mathbf{a}[j]-\mathbf{b}[j]\big{|}-\big{|}2r+\epsilon(\ell-2r)-2\epsilon\delta\big{|}\geq\big{(}1-2r-\epsilon(\ell-2r)+2\epsilon\delta\big{)}\geq
2r+\epsilon\delta$ where we have used the triangle inequality along with the
bounds $r=\frac{1}{4},\big{|}\mathbf{a}[j]-\mathbf{b}[j]\big{|}\geq
1,\ell\in[\delta]$ and $\epsilon\delta=\frac{1}{8d\delta}\leq\frac{1}{8}$.
Hence, square of the distance between the points $w$ and
$B_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{(}2r+\epsilon\delta\big{)}^{2}+(r-\epsilon/4)^{2}$
(only considering coordinates $i$ and $j$)
$\displaystyle\geq\big{(}2r+\epsilon\delta\big{)}^{2}$
$\displaystyle\geq\big{(}2r(1+\epsilon)\big{)}^{2}$ (from Equation 1 and
Equation 2)

    4. (iv)

$i=i^{\prime}=j$ : Since $\mathbf{a}[i^{\prime}]\neq\mathbf{b}[i^{\prime}]$ it
follows that $|\mathbf{a}[i]-\mathbf{b}[i]|\geq 1$. Hence, the distance
between centers of $T$ and $C_{\\_}{\mathbf{a}}^{+i}$ is

$\displaystyle\geq\big{|}(\mathbf{a}[i]+r-\epsilon/4)-\big{(}\mathbf{b}[i]+2r+\epsilon\cdot(\ell-2r)\big{)}\big{|}$
(only considering $i$-th coordinate)
$\displaystyle=\big{|}(\mathbf{a}[i]-\mathbf{b}[i])-\big{(}r+\epsilon\cdot(\ell-2r)+\epsilon/4\big{)}\big{|}$
$\displaystyle\geq|\mathbf{a}[i]-\mathbf{b}[i]|-\big{|}r+\epsilon\cdot(\ell-2r)+\epsilon/4\big{|}$
(by triangle inequality) $\displaystyle\geq
1-\big{(}r+\epsilon\cdot(\ell-2r)+\epsilon/4\big{)}$ (from
$|\mathbf{a}[i]-\mathbf{b}[i]|\geq 1,\ell\in[\delta]$ and Equation 1)
$\displaystyle\geq 2r(1+\epsilon)$ (from $\ell\in[\delta]$, Equation 1 and
Equation 2)

This completes the proof of the first part of the lemma. The proof of the
second part of the lemma is similar, and we omit the details here. ∎