# Coresets for Clustering in Geometric Intersection Graphs

Sayan Bandyapadhyay Portland State University, Oregon, USA. Fedor V. Fomin
University of Bergen, Norway. Tanmay Inamdar 00footnotemark: 0 The research
leading to these results has received funding from the Research Council of
Norway via the project BWCA (grant no. 314528), and the European Research
Council (ERC) via grant LOPPRE, reference 819416.

###### Abstract

Designing coresets—small-space sketches of the data preserving cost of the
solutions within $(1\pm\epsilon)$-approximate factor—is an important research
direction in the study of center-based $k$-clustering problems, such as
$k$-means or $k$-median. Feldman and Langberg [STOC'11] have shown that for
$k$-clustering of $n$ points in general metrics, it is possible to obtain
coresets whose size depends logarithmically in $n$. Moreover, such a
dependency in $n$ is inevitable in general metrics. A significant amount of
recent work in the area is devoted to obtaining coresests whose sizes are
independent of $n$ for special metrics, like $d$-dimensional Euclidean space
[Huang, Vishnoi, STOC'20], doubling metrics [Huang, Jiang, Li, Wu, FOCS'18],
metrics of graphs of bounded treewidth [Baker, Braverman, Huang, Jiang,
Krauthgamer, Wu, ICML’20], or graphs excluding a fixed minor [Braverman,
Jiang, Krauthgamer, Wu, SODA’21].

In this paper, we provide the first constructions of coresets whose size does
not depend on $n$ for $k$-clustering in the metrics induced by _geometric
intersection graphs_. For example, we obtain
$\frac{k\log^{2}k}{\epsilon^{\mathcal{O}(1)}}$ size coresets for
$k$-clustering in Euclidean-weighted unit-disk graphs (UDGs) and unit-square
graphs (USGs). These constructions follow from a general theorem that
identifies two canonical properties of a graph metric sufficient for obtaining
coresets whose size is independent of $n$. The proof of our theorem builds on
the recent work of Cohen-Addad, Saulpic, and Schwiegelshohn [STOC '21], which
ensures small-sized coresets conditioned on the existence of an interesting
set of centers, called _centroid set_. The main technical contribution of our
work is the proof of the existence of such a small-sized centroid set for
graphs that satisfy two canonical geometric properties. Loosely speaking, we
exploit the fact that the metrics of geometric intersection graphs are
``similar'' to the Euclidean metrics for points that are close, and to the
shortest path metrics of planar graphs for points that are far apart. The main
technical challenge in constructing centroid sets of small sizes is in
combining these two very different metrics.

The new coreset construction helps to design the first
$(1+\epsilon)$-approximation for center-based clustering problems in UDGs and
USGs, that is fixed-parameter tractable in $k$ and $\epsilon$ (FPT-AS).

##  1 Introduction

Clustering is one of the most important data analysis techniques where the
goal is to partition a dataset into a number of groups such that each group
contains similar set of data points. The notion of similarity is captured by a
distance function between the data points, and the goal of retrieving the best
natural clustering of the data points is achieved by minimizing a proxy cost
function. In this work, we study the popular $(k,z)$-clustering problem.

$(k,z)$-clustering. Given a set of points $P$ in a metric space
$(\Omega,\mathsf{d})$ and two positive integers $k$ and $z$, find a set $C$ of
$k$ points (or centers) in $\Omega$ that minimizes the following cost
function:

$\mathsf{cost}(C)=\sum_{p\in P}\mathsf{cost}(p,C)$

where $\mathsf{cost}(p,C)=(\mathsf{d}(p,C))^{z}$ and
$\mathsf{d}(p,C)=\min_{c\in C}\mathsf{d}(p,c)$.

Two widely studied clustering problems, $k$-means, and $k$-median clustering,
are special versions of $(k,z)$-clustering with $z=2$ and $z=1$, respectively.
A popular way of dealing with large data for the purpose of the analysis is to
apply a data reduction scheme as a preprocessing step. In the context of
clustering, one such way of preprocessing the data is to construct an object
known as _coresets_.

Coresets. Informally, an $\epsilon$-coreset for $(k,z)$-clustering is a small-
sized summary of the data that approximately (within $(1\pm\epsilon)$ factor)
preserves the cost of clustering with respect to any set of $k$ centers (we
will often shorten ``$\epsilon$-coreset'' to simply ``coreset''). Thus, any
solution set of centers on the coreset points can be readily used as a
solution for the original dataset. A formal definition follows.

######  Definition 1 ($\epsilon$-Coreset).

A coreset for $(k,z)$-clustering problem on a set $P$ of points in a metric
space $(\Omega,\mathsf{d})$ is a weighted subset $Y$ of $\Omega$ with weights
$\omega:Y\to^{+}$ such that for any set $\mathcal{S}\subseteq\Omega$ with
$|\mathcal{S}|=k$,

$\left|\sum_{p\in P}\mathsf{cost}(p,\mathcal{S})-\sum_{p\in
Y}\omega(p)\mathsf{cost}(p,\mathcal{S})\right|\leq\epsilon\cdot\sum_{p\in
P}\mathsf{cost}(p,\mathcal{S}).$

Feldman and Langberg [20] showed that for $n$ points in any general metric, a
coreset of size $\mathcal{O}(\epsilon^{-2z}k\log k\log n)$ can be constructed
in time $\tilde{\mathcal{O}}(nk)$, where $\tilde{\mathcal{O}}()$ notation
hides a poly-logarithmic factor. Also, it is known that the dependency on
$\log n$ in the above bound cannot be avoided [3, 18]. However, for several
special metrics, it is possible to construct coresets whose size does not
depend on the data size. There has been a large pool of work for Euclidean
spaces, culminating in a bound of $\mathcal{O}(k\cdot(\log
k)^{\mathcal{O}(1)}\cdot 2^{\mathcal{O}(z\log
z)}\epsilon^{-2}\cdot\min\\{\epsilon^{-z},k\\})$ [18], which is independent of
the data size and dimension of the space. Moreover, the question has been
studied in other specialized settings such as doubling metrics [28], shortest-
path metrics in the graphs of bounded-treewidth [3], and graphs excluding a
fixed minor [9]. A recent result by Cohen-Addad et al. [18] gives a unified
framework that encompasses all these results. We note that, since the number
of distinct (weighted) points in coresets is usually much smaller (and
sometimes independent of) $n$, they naturally find applications in non-
sequential settings such as streaming [27, 14].

Let us remark that all known results about small coresets in graph metrics
strongly exploit the sparsity property of graphs such as bounded treewidth [3]
or excluding a fixed minor [9]. There is a very good reason for that. In a
complete graph, by setting suitable weights on the edges one can represent
_any_ general metric. Thus if a graph family contains large cliques,
clustering in such graphs is as difficult as in general metrics.

In this work, we are interested in coreset construction for edge-weighted
geometric intersection graphs with shortest-path metric. A geometric
intersection graph of a set of geometric objects contains a vertex for each
object and an edge corresponding to each pair of objects that have non-empty
intersection. (We note that for our purpose of designing algorithms, we do not
explicitly need the objects or their geometric representation. It is
sufficient to work with the graph representation as long as the edge-weights
are given.) In particular, geometric intersection graphs are a widely studied
model for ad-hoc communication and wireless sensor networks [41, 4, 35, 38,
32]. Notably, clustering is a common topology management method in such
networks. Grouping nodes are used as subroutines for executing various tasks
in a distributed manner and for resource management, see the survey [42] for
an overview of different clustering methods for wireless sensor networks.

Our work is motivated by the following question: ``Is it possible to exploit
the properties of geometric intersection graphs for obtaining coresets whose
size does not depend on the data size?'' In general, the answer to this
question is _no_. This is because geometric intersection graphs can contain
large cliques. Even for objects as simple as unit squares, the corresponding
intersection graph could be a clique, and, as we already noted, by setting
suitable weights on the edges of the clique, one can represent any metric.
Hence constructing coresets in geometric intersection graphs with arbitrary
edge weights is as difficult as in general metrics. Thus, we need to restrict
edge weights in some manner in order to obtain non-trivial coresets for
geometric intersection graphs. As an illustrative example, let us take a look
at Euclidean-weighted UDGs, a well-studied class of geometric intersection
graphs.

Euclidean-weighted unit-disk graph metric. A unit-disk graph (UDG) is defined
in the following way—there is a configuration of closed disks of radii 1 in
the plane and a one-to-one correspondence between the vertices and the centers
of the disks such that there is an edge between two vertices if and only if
the disks having the two corresponding centers intersect. The weight of an
edge is equal to the Euclidean distance between the two corresponding centers.
Euclidean-weighted UDGs have been well-studied in computational geometry [11,
25]. Apart from practical motivation, UDGs are interesting from theoretical
perspectives as well. On the one hand, being embedded on the plane they
resemble planar graphs when ``zoomed out'', but could contain large cliques
locally. On the other hand, the metric induced by them is an amalgamation of
geometric and graphic settings, as it is locally Euclidean but globally a
graph metric. Due to the latter property, UDG metric can be used for fine-
tuned clustering, as with pure Euclidean distances one can only retrieve
clusters induced by convex partitions of the space (see Figure 1).

Figure 1: (Left.) A point set in 2D. (Middle.) $2$-means clustering with
Euclidean distances. Centers are shown by crosses. Points of two clusters are
shown by disks (red) and squares (blue). (Right.) $2$-means clustering on UDG
– due to the $3\sqrt{2}$ diagonal path distance, all the blue points (squares)
are closer to the upper center.

###  1.1 Our Results.

We now formalize our intuition about the ``hybrid'' nature about the Euclidean
weighted UDGs, by identifying two canonical geometric properties of a graph
$G$ that are sufficient for constructing small-sized coresets. For better
exposition, we fix a few notations. For any subgraph $H$ of $G$, we denote its
set of vertices and set of edges by $V(H)$ and $E(H)$, respectively. For
vertex set $V^{\prime}\subseteq V$, we denote by $G[V^{\prime}]$ the subgraph
of $G$ induced by $V^{\prime}$. For a subgraph $H$ of $G$, and $u,v\in V(H)$,
let $\pi_{H}(u,v)$ denote a shortest path between $u$ and $v$ (according to
the edge-weights in $G$ restricted to $H$) that uses the edges of $H$, and let
$\mathsf{d}_{H}(u,v)$ denote the weight of $\pi_{H}(u,v)$, i.e., the sum of
the weights of the edges along $\pi_{H}(u,v)$. For any path $\pi$ in a graph,
let $|\pi|$ denote the number of edges on $\pi$. Note that $\mathsf{d}_{H}$ is
the so-called _shortest path metric_ on $H$. Finally, for any pair of points
$p,q\in^{2}$, let $|pq|$ denote the euclidean (i.e., $\ell_{2}$-norm) distance
between $p$ and $q$.

Canonical geometric properties.
(1) Locally Euclidean: There exist (not necessarily distinct) constants
$c_{1},c_{2},c_{3},c_{4}\geq 0$, such that the following holds. $G$ has an
embedding $\lambda:V(G)\to^{2}$ in the plane such that the vertices of $G$ are
mapped to points in the plane, with the following two properties.

  1. 1.

For any two $u,v\in V(G)$, if $|\lambda(u)\lambda(v)|\leq c_{1}$ then $uv\in
E(G)$, and for any $u^{\prime},v^{\prime}\in V(G)$, if
$|\lambda(u^{\prime})\lambda(v^{\prime})|_{2}>c_{2}$, then
$u^{\prime}v^{\prime}\not\in E(G)$.

  2. 2.

For any $u,v\in V(G)$ such that $uv\in E(G)$, let $w(uv)$ denote the weight of
the edge $uv$. Then, the edge $uv$ is a shortest path between $u$ and $v$ in
$G$.
Furthermore, $c_{3}\cdot|\lambda(u)\lambda(v)|\leq w(uv)\leq
c_{4}\cdot|\lambda(u)\lambda(v)|$.

(2) Planar Spanner: For any induced subgraph $G^{\prime}=G[V^{\prime}]$ with
$V^{\prime}\subseteq V(G)$, there exists a planar $\alpha$-spanner
$H^{\prime}=(V^{\prime},E(H^{\prime}))$ for some fixed $\alpha\geq 1$, i.e.,
(i) $H^{\prime}$ is a subgraph of $G^{\prime}$ (and hence of $G$) –
$E(H^{\prime})\subseteq E(G^{\prime})$, and (ii) for any $u,v\in V^{\prime}$,
$\mathsf{d}_{G^{\prime}}(u,v)\leq\mathsf{d}_{H^{\prime}}(u,v)\leq\alpha\cdot\mathsf{d}_{G^{\prime}}(u,v)$.

Our main result is the following theorem.

######  Theorem 1 (Informal).

Consider the metric space $(V,\mathsf{d}_{G})$ induced by any graph $G$
satisfying the two canonical geometric properties (1) and (2), and a set
$P\subseteq V(G)$. Then there exists a polynomial time algorithm that
constructs a coreset for $(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k)$, where $\beta=\mathcal{O}(z\log
z)$.

Theorem 1 is a handy tool to construct coresets for several interesting
geometric intersection graphs coupled with suitable metrics. First, let us
observe that our initial example, namely, a metric induced by a Euclidean-
weighted UDG $G$ satisfies the two canonical properties. Consider an embedding
of $G$ in 2. Note that there is an edge between any two points iff the
Euclidean distance between the two points is at most $2$, and the weight of
such an edge is exactly the euclidean distance. Thus, $G$ is Locally Euclidean
with $c_{1}=c_{2}=2$, and $c_{3}=c_{4}=1$. Furthermore, due to a result of Li,
Calinescu, and Wan [37], any Euclidean-weighted UDG admits a constant-stretch
planar spanner (cf. Proposition 6). Thus, $G$ also satisfies the Planar
Spanner property. Therefore, due to Theorem 1, we can obtain
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k)$-size coresets for
$(k,z)$-clustering on Euclidean-weighted UDGs. In the following, we discuss
further applications of our framework.

$\ell_{\infty}$-weighted unit-square graph metric. Unit-square graphs (USGs)
are similar to UDGs except they are defined as intersection graphs of (axis-
parallel) unit squares instead of unit disks 111Although it might seem
unnatural at first, it is convenient to define a _unit square_ as a square of
sidelength $2$. This is analogous to a unit disk being a disk of diameter $2$.
In either case, the class of USGs remains unaffected by scaling.. Indeed,
these two graph classes are distinct. For example, the $K_{1,5}$ claw can be
realized by a UDG, but not by any USG. (See Figure 2.) Since a unit square is
a ``unit ball'' in $\ell_{\infty}$-norm, it is more natural to consider
$\ell_{\infty}$ weights on the edges. It is not too difficult to see that the
Locally Euclidean property holds for $\ell_{\infty}$-weighted USGs – we give a
formal proof in Section 4.2. On the other hand, in order to establish the
second property, we have to prove the existence of a constant-stretch planar
spanner for USGs. To the best of our knowledge this result was previously not
known and is of independent interest. We show this result in Section 5. Thus,
$\ell_{\infty}$ weighted USGs also satisfy the two properties required to
apply Theorem 1 in order to obtain a small-sized coreset.

Figure 2: Figure showing a set of disks realizing $K_{1,5}$ and a set of
squares realizing $K_{1,4}$. Two pairs of intersecting unit squares must
contain a corner of each other, and so the central square can intersect with
at most four other unit squares that are pairwise disjoint.

Other extensions. In 2, all $\ell_{p}$ distances ($1\leq p\leq\infty$) are
within a $\sqrt{2}$ factor from each other. Thus, our arguments can be easily
extended to any $\ell_{p}$ weights on UDGs/USGs for any $1\leq p\leq\infty$
without any changes on the bounds. We formally prove this in Section 4.3.
Lastly, we consider shortest-path metrics in unweighted (i.e., hop-distance)
unit-disk graphs of bounded maximum degree. Notably, these graphs satisfy the
Planar Spanner property due to a result of [7]. Nevertheless, we show in
Section 4.4 that we can modify our approach to construct a small-sized coreset
for such metrics. To summarize, we obtain coresets for $(k,z)$-clustering with
size independent of $n$ for the following graph metrics.

  * •

$\ell_{p}$-distance weighted UDGs for any $1\leq p\leq\infty$,

  * •

$\ell_{p}$-distance weighted USGs for any $1\leq p\leq\infty$,

  * •

Bounded-degree unweighted UDGs.

FPT Approximation Schemes. As a corollary to Theorem 1, we obtain
$(1+\epsilon)$-approximations for $(k,z)$-clustering in geometric intersection
graphs that are fixed-parameter tractable (FPT) in $k$ and $\epsilon$. Note
that such a $(1+\epsilon)$-approximation was not known before even for UDGs,
as it does not follow from previously known bound on coreset sizes. Prior to
our work, the best known bound for UDGs — as in general metrics — was $O(k\log
n\cdot\epsilon^{-\max(2,z)})$ [19]. We note that even though a coreset reduces
the number of distinct points (or clients) to be clustered, the number of
potential centers (or facilities) still remains the same, i.e., $n$. Hence, a
coreset does not directly help us enumerate all possible sets of $k$ centers
from which we could pick the best set. An alternative way to enumerate these
sets of centers is to enumerate all possible partitions (or clusterings) of
the coreset points. Note that each clustering of coreset points corresponds to
a clustering of the original points, and the cost of clustering is preserved
to within a $(1\pm\epsilon)$ factor. With our coreset bound of
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k)$, the number of distinct clusterings
is only $k^{\mathcal{O}(\epsilon^{-\beta}k\log^{2}k)}$. As the time complexity
is dominated by the computations of cluster centers and costs for all the
partitions, overall the algorithm takes
$k^{\mathcal{O}(\epsilon^{-\beta}k\log^{2}k)}n^{\mathcal{O}(1)}$ time.

######  Corollary 1.

For each of the metrics listed in the above, there exists a
$(1+\epsilon)$-approximation for $(k,z)$-clustering with $z\geq 1$ that runs
in time $2^{\mathcal{O}(\epsilon^{-\beta}k\log^{3}k)}n^{\mathcal{O}(1)}$,
where $\beta=\mathcal{O}(z\log z)$.

###  1.2 General overview of the methods

Our coreset construction is based on a recent work due to Cohen-Addad,
Saulpic, and Schwiegelshohn [19], which gives a framework for constructing
coresets in various settings.The essence of the framework is that it
translates the problem of coreset construction to showing the existence of an
interesting set of centers or centroid set. In particular, consider any set
$\mathcal{S}$ of $k$ centers and any subset $X\subseteq P$ of points that are
sufficiently close to $\mathcal{S}$ compared to an existing solution
$\mathcal{A}$. Then a subset $\mathbb{C}\subseteq\Omega$ is a _centroid set_
for $P$ if it contains centers that well-approximates $\mathcal{S}$, i.e.,
there exists $\tilde{\mathcal{S}}\subseteq\mathbb{C}$, such that for every
$p\in X$, it holds that
$|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|\leq{\epsilon}(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A}))$.
The framework informally states that if there is a centroid set $\mathbb{C}$,
then a coreset can be constructed whose size depends logarithmically on
$|\mathbb{C}|$. Such a dependency arises in their randomized construction in
order to prove a union bound over all possible interesting solutions, which
can be at most $|\mathbb{C}|^{k}$. By showing the existence of small-sized
centroid sets, they obtain improved coreset size bounds for a wide range of
spaces.

We use the framework of Cohen-Addad et al. for our coreset construction. Our
main technical result shows if for a graph $G$ with metric $\mathsf{d}_{G}$,
the two canonical geometric properties are satisfied, then there exists a
small-sized centroid set for $G$. This is the most challenging part of the
proof and it requires a novel combination of tools and techniques from
computational geometry. As soon as we establish the existence of the centroid
set, the construction of coresets follows the steps of [19]. For the sake of
exposition, let us consider a concrete example of Euclidean-weighted UDGs.

The first hurdle one faces while dealing with UDGs is that they encapsulate a
combination of the Euclidean case and the case of _graphical_ or shortest-path
metric. For example, consider any cluster of points with cluster center $s$.
The points that are nearby (i.e., within distance $2$) $s$ behave simply as
points in the Euclidean case. But, a point $p$ that is far away from $s$ can
have a shortest path distance which is much larger than the actual Euclidean
distance between $p$ and $s$, see Figure 1. We first show that it is possible
to conceptually separate out these two cases—but one has to be careful, as a
cluster can potentially contain both types of points. Notably, none of the
previous works had to deal with such a hybrid metric. To handle the set of
nearby points, we exploit the Locally Euclidean property. In particular, by
overlaying a grid of appropriately small sidelength, and selecting one
representative point from each cell of the grid, we can compute a centroid set
that preserves the distances from the nearby points.

In the other case, a shortest path between a point $p$ and a center $s$
consists of more than one edge, and we need to deal with a graphical metric.
This case is much more interesting. All other works establishing small-sized
centroid sets in certain graph metrics exploit the fact that certain graph
classes admit small or well-behaved separators. For example, bounded treewidth
graph admit separators bounded by treewidth; whereas graphs excluding a fixed
minor admit shortest path separators. However, UDGs may contain arbitrarily
large cliques, and therefore do not admit such separators in general. Thus, we
reach a technical bottleneck. Note that this is the first work of its kind
that handles such a dense graph. To overcome this challenge, we use the other
canonical property. Instead of directly working with the UDG, we consider its
planar spanner, where distances are preserved up to a constant factor. The
existence of such a spanner is guaranteed by the second canonical property,
Planar Spanner. As planar graphs have shortest path separators, now we can
apply the existing techniques. However, if we were to entirely rely on the
spanner, some of the distances may be scaled up by a constant ($>2$) factor in
the spanner, and thus it would not be possible to ensure the
$(1\pm\epsilon)$-factor bound required to construct a coreset.

Thus, we use the spanner as a supporting graph in the following way. First, we
recursively decompose the original UDG by making use of the shortest path
separators admitted by the planar spanner. We note that although planar graph
decomposition has been used in coreset literature, using such a guided scheme
to obtain a decomposition of a much more general graph is novel. Then, we use
this recursive decomposition of the UDG, along with the shortest path
separators used to find this decomposition, in order to construct the centroid
set. In this construction, we use the spanner in a restricted manner, and use
it such that error incurred by the use of the spanner is upper bounded by
$\alpha$ times the weight of at most one edge along a shortest path from a
point $p$ to its corresponding (approximate) center. However, observe that if
such a shortest path consists of a single edge, then even this error is too
large. To resolve this issue, we rely on the planar spanner, only if the
shortest path is ``long enough'', i.e., contains $\Omega(z/\epsilon)$ edges.
In this case, Locally Euclidean property implies that for such a ``long
path'', the _length_ of the path and the _number of edges_ on the path are
within a constant factor from each other. This implies that the error
introduced by rerouting a single edge using the spanner is at most $\epsilon$
times the length of the path, i.e., negligible.

Finally, if a shortest path between a point and a center consists of
$\mathcal{O}(z/\epsilon)$ edges, then we can use a modified version of the
grid-cell argument to obtain a small-sized centroid set.

We note that this is simply an intuitive overview of the challenges faced in
each of the three cases. The actual construction of the centroid set, and the
analysis of the error incurred in each of the cases is fairly convoluted.
While replacing a center $s\in\mathcal{S}$ by another one
$\tilde{s}\in\mathbb{C}$, we need to ensure that for a point $p$ having $s$ as
its closest center, $\mathsf{d}_{G}(p,\tilde{s})$ is neither too large nor too
small compared to $\mathsf{d}_{G}(p,s)$, since we want to bound the error in
the absolute difference. In addition, we have to be extremely careful while
combining the three centroid (sub)sets constructed for each of the cases, and
ensure that a good replacement $\tilde{s}$ found for a center $s$ in one of
the cases does not adversely distort the error for a point that is being
handled in another case.

Related work. Here we give an overview of the literature on coresets. For a
more exhaustive list, we refer to [19, 29]. Coreset construction was
popularized by an initial set of works that obtained small-sized coresets in
low-dimensional Euclidean spaces [27, 26, 23]. Chen [14] obtained the first
coreset for Euclidean spaces with polynomial dependence on the dimension and
the first coreset in general metrics, where the size is
$\mathcal{O}(k^{2}\epsilon^{-2}\log^{2}n)$ for $k$-median. Subsequently, the
dependence on the dimension has been further improved [34, 21]. Finally, such
dependence was removed in [22, 43]. See also [5, 19, 29, 9, 18] for recent
improvements.

Both $k$-median and $k$-means admit polynomial-time
$\mathcal{O}(1)$-approximations in general metrics [12, 13, 30, 36, 10, 1].
Moreover, algorithms with improved approximation guarantees can be obtained
that is FPT in $k$ and $\epsilon$ [16]. Naturally, the problems have also been
studied in specialized metrics. Polynomial-time approximation schemes (PTASes)
are known for Euclidean $k$-median [2] and $k$-means [17, 24]. See [15, 33]
for other improvements. Similar to geometric clustering, clustering in graphic
setting is also widely studied. PTASes are known for excluded-minor graphs
[17, 9]. Also, FPT approximation schemes are known for graphs of bounded-
treewidth [3] and graphs of bounded highway dimension [6, 9].

##  2 Coresets for Geometric Graphs

To set up the stage, we need the following definition of centroid set from
[19].

######  Definition 2 (Centroid Set).

Consider any metric space $(\Omega,\mathsf{d})$, a set of clients
$P\subseteq\Omega$, and two positive integers $k$ and $z$. Let $\epsilon>0$ be
a precision parameter. Given a set of centers $\mathcal{A}$, a set
$\mathbb{C}$ is an $\mathcal{A}$-approximate centroid set for
$(k,z)$-clustering on $P$ that satisfies the following property.

For every set of $k$ centers $\mathcal{S}\subseteq\Omega$, there exists
$\tilde{\mathcal{S}}\subseteq\mathbb{C}$, such that for every $p\in P$ that
satisfies
$\mathsf{cost}(p,\mathcal{S})\leq\left(\frac{10z}{\epsilon}\right)^{z}\cdot\mathsf{cost}(p,\mathcal{A})$
or
$\mathsf{cost}(p,\tilde{\mathcal{S}})\leq\left(\frac{10z}{\epsilon}\right)^{z}\cdot\mathsf{cost}(p,\mathcal{A})$,
it holds that

$|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|\leq\frac{\epsilon}{z\log(z/\epsilon)}(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A})).$

Informally, a centroid set $\mathbb{C}$ is a collection of candidate centers,
potentially much smaller than $\Omega$, such that the $k$ centers in
$\mathcal{S}$ can be replaced by $k$ centers in
$\tilde{\mathcal{S}}\subseteq\mathbb{C}$ without changing the cost of points
by a large amount, that are much closer to $\mathcal{S}$ or
$\tilde{\mathcal{S}}$ compared to $\mathcal{A}$ w.r.t. $\mathsf{d}$. They
proved that one can obtain coresets whose size depends only logarithmically on
the size of any such centroid set.

######  Proposition 1 ([19]).

Consider any metric space $(\Omega,\mathsf{d})$, a set of points
$P\subseteq\Omega$ with $n$ distinct points, and two positive integers $k$ and
$z$. Let $\epsilon>0$ be a precision parameter. Suppose $\mathcal{A}$ be a
given constant-factor approximation for $(k,z)$-clustering on $P$.

Suppose there exists an $\mathcal{A}$-approximate centroid set for
$(k,z)$-clustering on $P$. Then there exists a polynomial time algorithm that
constructs with probability at least $1-\delta$ a coreset of size

$\mathcal{O}\bigg{(}\frac{2^{\mathcal{O}(z\log
z)}\cdot\log^{4}(1/\epsilon)}{\min\\{\epsilon^{2},\epsilon^{z}\\}}(k\log|\mathbb{C}|+\log\log(1/\epsilon)+\log(1/\delta))\bigg{)}$

with positive weights for $(k,z)$-clustering on $P$.

First, note that the above coreset framework requires only the existence of
such a centroid set. It is not needed to explicitly compute it. Indeed, such a
centroid set is only used to bound the size of computed coresets in their
analysis.

Our main technical contribution is the theorem that guarantees the existence
of a small-sized centroid set when the geometric graph metrics satisfy two
canonical geometric properties.

######  Theorem 2.

(Centroid Set Theorem) Consider the metric space $(V,\mathsf{d}_{G})$ induced
by any graph $G=(V,E)$ satisfying the Locally Euclidean and Planar Spanner
properties defined before. Also consider a set of points $X\subseteq V$ and
two positive integers $k$ and $z\geq 1$. Let $\epsilon>0$ be the precision
parameter. Additionally, suppose $\mathcal{A}$ be a solution for
$(k,z)$-clustering on $X$. Then there exists an $\mathcal{A}$-approximate
centroid set $\mathbb{C}$ for $(k,z)$-clustering on $X$ of size
$\exp(\mathcal{O}(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|))$.

We prove Theorem 2 in the following section. Then the desired coreset result
follows by Proposition 1 and from [9], with some minor changes due to our
different bound on coreset-size. For completeness, we describe the proof.

######  Theorem 3.

Consider the metric space $(V,\mathsf{d}_{G})$ induced by any graph $G=(V,E)$
satisfying Locally Euclidean and Planar Spanner properties, a set $P\subseteq
V$ with $n$ distinct points, and two positive integers $k$ and $z\geq 1$. Then
there exists a polynomial time algorithm that constructs with probability at
least $1-\delta$ a coreset for $(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\mathcal{O}(z\log z)}k\log^{2}k\log^{3}(1/\delta))$,
where $z$ is a constant, and $\delta<1/4$.

###### Proof.

For proving the theorem, we apply the Iterative size reduction algorithm [9].
Let $t$ be the largest integer such that
$\log^{(t-1)}n\geq\max\\{125k\epsilon^{-\rho}\log(1/\delta),\rho
2^{\rho+1}\\}$ for a sufficiently large constant $\rho$ to be set later. Also,
let $X_{0}=P$. For $1\leq i\leq t$, set
$\epsilon_{i}=\epsilon/(\log^{(i)}n)^{1/\rho}$ and
$\delta_{i}=\delta/|X_{i-1}|$. Let $X_{i}$ be the coreset computed by applying
the algorithm of Proposition 1 on the client set $X_{i-1}$ with $\epsilon$
being $\epsilon_{i}$ and $\delta$ being $\delta_{i}$ for $1\leq i\leq t$.
Finally, let $U$ be the coreset returned by applying the same algorithm on
$X_{t}$ with approximation guarantee $1+\epsilon$ and failure probability
$\delta$.

First we argue about the rate of decrement in coreset sizes between two
consecutive iterations. Let $n_{i}$ be the size of $X_{i}$ for $1\leq i\leq
t$. Then,

$\displaystyle n_{i}$ $\displaystyle=\frac{2^{\mathcal{O}(z\log
z)}\cdot\log^{4}(1/\epsilon_{i})}{\min\\{\epsilon_{i}^{2},\epsilon_{i}^{z}\\}}(k\log|\mathbb{C}_{i}|+\log\log(1/\epsilon_{i})+\log(1/\delta_{i}))$
($\mathbb{C}_{i}$ is the centroid set w.r.t. $X_{i}$)
$\displaystyle=\frac{2^{\mathcal{O}(z\log
z)}\cdot\log^{4}(1/\epsilon_{i})}{\min\\{\epsilon_{i}^{2},\epsilon_{i}^{z}\\}}(k\log^{2}n_{i-1}+kz^{9}\epsilon_{i}^{-5}\log
n_{i-1}+\log\log(1/\epsilon_{i})+\log(1/\delta_{i}))$
$\displaystyle\leq\epsilon_{i}^{-\alpha}k\log^{2}n_{i-1}\log(1/\delta_{i})$
($\alpha=\mathcal{O}(z\log z)$)
$\displaystyle\leq\epsilon_{i}^{-\alpha}k\log^{2}n_{i-1}(\log
n_{i-1}+\log(1/\delta))$
$\displaystyle\leq\epsilon_{i}^{-\alpha}k\log^{3}n_{i-1}\log(1/\delta)$

The last inequality follows, as $n_{i-1}\geq 4$ and $\delta<1/4$. Let
$\Gamma=k\epsilon^{-\alpha}\log(1/\delta)$. Next, we prove that $n_{i}\leq
125\Gamma(\log^{(i)}n)^{4}$ for $1\leq i\leq t$. We use induction on $i$. In
the base case,
$n_{1}\leq\epsilon_{1}^{-\alpha}k\log^{3}n\log(1/\delta)=k\epsilon^{-\alpha}\log(1/\delta)(\log
n)^{\alpha/\rho}\log^{3}n=\Gamma\log^{4}n\leq 125\Gamma\log^{4}n$. The second
last equality follows by setting the value of $\rho$ to be equal to $\alpha$.
Now, consider any $i\geq 2$.

$\displaystyle n_{i}$
$\displaystyle\leq\epsilon_{i}^{-\alpha}k\log^{3}n_{i-1}\log(1/\delta)$
$\displaystyle\leq(\epsilon/(\log^{(i)}n)^{1/\rho})^{-\alpha}k\log^{3}n_{i-1}\log(1/\delta)$
$\displaystyle=k\epsilon^{-\alpha}\log(1/\delta)(\log^{(i)}n)^{\alpha/\rho}\log^{3}n_{i-1}$
$\displaystyle=\Gamma(\log^{(i)}n)\log^{3}n_{i-1}$ (as $\rho=\alpha$)
$\displaystyle\leq\Gamma(\log^{(i)}n)(\log(125\Gamma(\log^{(i-1)}n)^{4}))^{3}$
$\displaystyle\leq\Gamma(\log^{(i)}n)(\log(125\Gamma)+4\log^{(i)}n)^{3}$
$\displaystyle\leq\Gamma(\log^{(i)}n)(\log^{(i)}n+4\log^{(i)}n)^{3}$ (by
definition of $t$, $\log^{(i-1)}n\geq
125k\epsilon^{-\rho}\log(1/\delta)=125\Gamma$)
$\displaystyle=125\Gamma(\log^{(i)}n)^{4}$

It follows that $n_{t}\leq 125\Gamma(\log^{(t)}n)^{4}$. Now, by definition of
$t$, $\log^{(t)}n<\max\\{125\Gamma,\rho 2^{\rho+1}\\}$. Hence,
$n_{t}\leq\max\\{(125\Gamma)^{5},125\Gamma(\rho 2^{\rho+1})^{4}\\}$. Next, we
analyze the error in the following claim.

######  Claim 1.

$\prod_{i=1}^{t}(1+\epsilon_{i})\leq 1+10\epsilon$.

###### Proof.

By definition, $X_{t}$ is a coreset with approximation guarantee at most
$\Pi_{i=1}^{t}(1+\epsilon_{i})$. Now, by our assumption,
$\log^{(i-1)}n\geq\rho 2^{\rho+1}$ for $i\leq t$. For such value of
$\log^{(i-1)}n$,

$\displaystyle\log^{(i-1)}n\geq 2^{\rho}\log^{(i)}n$
$\displaystyle\Rightarrow(\log^{(i-1)}n)^{1/\rho}\geq 2(\log^{(i)}n)^{1/\rho}$
$\displaystyle\Rightarrow\epsilon/(\log^{(i-1)}n)^{1/\rho}\leq(1/2)\cdot(\epsilon/(\log^{(i)}n)^{1/\rho})$
$\displaystyle\Rightarrow\epsilon_{i}\geq 2\epsilon_{i-1}$
$\displaystyle\Rightarrow\sum_{i=1}^{t}\epsilon_{i}\leq 2\epsilon_{t}$

It follows that

$\prod_{i=1}^{t}(1+\epsilon_{i})\leq\exp\left(\sum_{i=1}^{t}\epsilon_{i}\right)\leq\exp\left(2\epsilon_{t}\right)\leq\exp\left(\frac{2\epsilon}{(\log^{(t)}n)^{1/\rho}}\right)\leq\exp\left(2\epsilon\right)\leq
1+10\epsilon.$

The second last inequality follows from the fact that $\log^{(t)}n\geq 1$,
which is true as $\log^{(t-1)}n\geq\rho 2^{\rho+1}$. ∎

Next, we analyze the failure probability. First note that we can assume that
the size of $X_{i-1}$ is at least $\log^{(i-1)}n$. Otherwise, we can add
arbitrary points to the coreset $X_{i-1}$ and increase its size. Hence,
$n_{i-1}\geq\log^{(i-1)}n$. Then,
$\delta_{i}=\delta/n_{i-1}\leq\delta/\log^{(i-1)}n$. So, the total failure
probability is at most,

$\sum_{i=1}^{t}\delta_{i}=\delta\left(\frac{1}{n}+\frac{1}{\log
n}+\ldots+\frac{1}{\log^{(t-1)}n}\right)=\mathcal{O}(\delta)$

The last inequality follows, as $\log^{(t-1)}n\geq\rho 2^{\rho+1}\geq 4$.

In the above we showed that $X_{t}$ is a coreset of size at most
$\max\\{(125\Gamma)^{5},125\Gamma(\rho 2^{\rho+1})^{4}\\}$ with approximation
guarantee $1+\mathcal{O}(\epsilon)$ and failure probability at most
$\mathcal{O}(\delta)$. Hence, the set $U$ obtained by applying the algorithm
of Proposition 1 on $X_{t}$ is a coreset with approximation guarantee
$1+\mathcal{O}(\epsilon)$, failure probability at most $\mathcal{O}(\delta)$
and size at most

$\displaystyle\epsilon^{-\alpha}k\log^{2}|X_{t}|\log(1/\delta)$
$\displaystyle=\mathcal{O}(\epsilon^{-\alpha}k\log(1/\delta)\log^{2}\Gamma)$
$\displaystyle=\mathcal{O}(\epsilon^{-\alpha}k\log(1/\delta)(\log
k+\log(1/\epsilon)+\log\log(1/\delta))^{2})$
$\displaystyle=\mathcal{O}(\epsilon^{-\beta}k\log^{2}k\log^{3}(1/\delta))$

where $\beta=\mathcal{O}(\alpha)=\mathcal{O}(z\log z)$. Scaling $\epsilon$ and
$\delta$ by constants we obtain the desired bound. Finally, as
$t+1=\mathcal{O}(\log^{*}n)$, we apply the $\mathcal{O}(n)$ time algorithm in
Proposition 1 $\mathcal{O}(\log^{*}n)$ times. Moreover, we need to compute an
approximate solution $\mathcal{A}$ in order to apply this algorithm. For this
purpose, we use the $\tilde{\mathcal{O}}(nk)$ time algorithm of Mettu and
Plaxton [40] that returns a constant approximation. ∎

##  3 Proof of the Centroid Set Theorem

In this section, we prove our main result, existence of a small-sized centroid
set. Recall that we are given $G=(V,E)$, a connected, undirected, and edge-
weighted graph on $n$ vertices. Moreover, $G$ satisfies two canonical
geometric properties: (1) Locally Euclidean, and (2) Planar Spanner.

As $(V,\mathsf{d}_{G})$ is our metric space, we use the terms points and
vertices interchangeably. $X\subseteq V$ is the given set of points. We are
also given $\mathcal{A}$, a solution for $(k,z)$-clustering on $X$. We prove
that there exists an $\mathcal{A}$-approximate centroid set of size
$\exp(\mathcal{O}(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|))$
for $(k,z)$-clustering on $X$, which satisfies the following property.

For every set of $k$ centers $\mathcal{S}\subseteq V$, there exists
$\tilde{\mathcal{S}}\subseteq\mathbb{C}$, such that for every $p\in X$ that
satisfies
$\mathsf{cost}(p,\mathcal{S})\leq\left(\frac{10z}{\epsilon}\right)^{z}\cdot\mathsf{cost}(p,\mathcal{A})$
or
$\mathsf{cost}(p,\tilde{\mathcal{S}})\leq\left(\frac{10z}{\epsilon}\right)^{z}\cdot\mathsf{cost}(p,\mathcal{A})$,
it holds that

$|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|\leq\frac{\epsilon}{z\log(z/\epsilon)}(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A})).$

###  3.1 Useful Properties

In the analysis, we will use a few consequences of the Locally Euclidean
property, which we state in the following.

######  Proposition 2 (Bounded Distance.).

There exist universal constants $c^{\prime}_{1},c^{\prime}_{2}$ such that, the
weight of any edge of $G$ is at most $c^{\prime}_{2}$, and for any $\tau\geq
2$, and for any $u,v\in V(G)$, if $|\pi_{G}(u,v)|=\tau$, then
$\mathsf{d}_{G}(u,v)\geq c^{\prime}_{1}\tau$. That is,
$\mathsf{d}_{G}(u,v)=\Theta(\tau)$ for $\tau\geq 2$.

###### Proof.

Let $c_{1},c_{2},c_{3},c_{4}\geq 0$ be the constants such that $G$ and the
embedding $\lambda$ satisfies the Locally Euclidean property. Consider an edge
$uv\in E(G)$. It follows that $|\lambda(u)\lambda(v)|\leq c_{1}$, which
implies that $w(uv)\leq c_{4}\cdot|\lambda(u)\lambda(v)|\leq c_{4}\cdot
c_{1}$. Hence, the weight of any edge is bounded by $c^{\prime}_{2}\coloneqq
c_{1}\cdot c_{4}$.

Now, consider a minimum-hop shortest path
$\pi(u,v)=(u=w_{0},w_{1},\ldots,w_{\tau}=v)$, where $\tau\geq 1$. For any
$0\leq i\leq t-2$, observe that $w_{i}w_{i+2}\not\in E(G)$ – otherwise we can
short-cut and obtain a path of smaller length as well as smaller number of
hops. This implies that, $|\lambda(w_{i})\lambda(w_{i+2})|>c_{1}$. Then, by
triangle inequality, it follows that
$|\lambda(w_{i})\lambda(w_{i+1})|+|\lambda(w_{i+1})\lambda(w_{i+2})|>c_{1}$.
On the other hand,
$\mathsf{d}_{G}(w_{i},w_{i+2})=\mathsf{d}_{G}(w_{i},w_{i+1})+\mathsf{d}_{G}(w_{i+1},w_{i+2})\geq
c_{3}\cdot(|\lambda(w_{i})\lambda(w_{i+1})|+|\lambda(w_{i+1})\lambda(w_{i+2})|)>c_{3}\cdot
c_{1}$. That is, the length of each sub-path of $\pi(u,v)$ of length $2$ is at
least a constant. It follows that, $\mathsf{d}_{G}(u,v)\geq c_{3}\cdot
c_{1}\cdot\lfloor\tau/2\rfloor\geq c^{\prime}_{1}\cdot\tau$ if $\tau\geq 2$. ∎

######  Proposition 3 (Construction of $\mu$-net).

Let $0<\mu<c_{1}/\sqrt{2}$, and $t\geq 0$. Then, for any $v\in V(G)$, let
$B(v,r)=\\{u\in V(G):\mathsf{d}_{G}(u,v)\leq r\\}$. Then, there exists a
subset $B^{\prime}\subseteq B(v,r)$ of size $\mathcal{O}(r^{2}/\mu^{2})$ such
that for any $u\in B(v,r)$, there exists $u^{\prime}\in B^{\prime}$ such that
$\mathsf{d}_{G}(u,u^{\prime})=\mathcal{O}(\mu)$. Such a set $B^{\prime}$ is
called a $\mu$-net of $B(v,r)$.

###### Proof.

Consider an embedding $\lambda:V(G)\to^{2}$ guaranteed by Locally Euclidean
property. Consider a grid of sidelength $\mu<c_{1}\sqrt{2}$. It follows that
for any two points contained in a grid cell, the corresponding vertices are
neighbors in $G$. Furthermore, for any neighbors $u,v\in V(G)$, it follows
that $|\lambda(v)\lambda(f(v))|\leq\sqrt{2}\mu\leq c_{1}$, which implies that
$\mathsf{d}_{G}(v,f(v))=w(vf(v))\leq c_{4}\cdot|\lambda(v)f(v)|\leq
c_{4}\cdot\sqrt{2}\mu=\mathcal{O}(\mu)$. To construct $B^{\prime}$, we
arbitrarily select one point from each cell $C\cap B(v,r)$, provided that
$C\cap B(v,r)\neq\emptyset$.

To bound the size of $B^{\prime}$, we consider two cases. If $r\leq c_{1}$,
then all vertices in $B(v,r)$ are neighbors of $v$. It follows that all the
corresponding points are contained in a disk of radius $r/c_{3}$ around
$\lambda(v)$. The number of grid cells of sidelength $\mu$ contained in this
disk can be upper bounded by $\mathcal{O}(r^{2}/\mu^{2})$, and we add one
point from each such cell to $B^{\prime}$. If $c_{1}<r<c_{2}$, then we can
again use a similar argument to upper bound the number of cells by
$\mathcal{O}(c_{2}^{2}/\mu^{2})=\mathcal{O}(r^{2}/\mu^{2})$.

Otherwise, suppose $r>c_{2}$. Consider a vertex $w$ such that
$\mathsf{d}_{G}(v,w)\leq r$, but $v$ and $w$ are not neighbors in $G$. It
follows that $|\pi_{G}(v,w)|=\tau\geq 2$. It follows that
$|\lambda(v)\lambda(w)|\leq c_{4}\tau$. On the other hand, Proposition 2
implies that $\mathsf{d}_{G}(v,w)\geq c^{\prime}_{1}\tau$. This implies that
$|\lambda(v)\lambda(w)|\leq(c_{4}/c^{\prime}_{1})\cdot r$. It follows that a
point corresponding to a vertex in $B(v,r)$ is contained in a disk of radius
$\mathcal{O}(r)$ around $\lambda(v)$. The number of cells of sidelength $\mu$
inside this disk is $\mathcal{O}(r^{2}/\mu^{2})$. ∎

######  Proposition 4 (Bounded Degree Support Graph).

For any _precision value_ $0<\mu<c_{1}/\sqrt{2}$, there exists a graph $H$
with the following properties (i) $V(H)\subseteq V(G)$, the maximum vertex
degree of $H$ is bounded by a polynomial function
$\Delta(1/\mu)=\mathcal{O}(1/\mu^{2})$, and (iii) there is a mapping
$f:V(G)\rightarrow V(H)$ such that for any $v\in V(G)$,
$\mathsf{d}_{G}(v,f(v))=\mathcal{O}(\epsilon)$ and for any path
$u_{1},u_{2},\ldots,u_{t}$ of $G$, $H$ contains the path
$f(u_{1}),f(u_{2}),\ldots,f(u_{t})$.

###### Proof.

Consider a gridcell of sidelength $\mu$ as in the previous proposition, which
implies that any two points belonging to a grid cell are neighbors in $G$.
Now, we construct support graph $H$ in the following way. We select any
arbitrary point from each grid cell that contains a point in $V(G)$ and add
this special point to $V(H)$. The mapping $f$ is constructed in the following
way. Map each vertex $v\in V(G)$ to the special point of the grid cell that
contains $v$. It follows that $|\lambda(v)\lambda(f(v))|\leq\sqrt{2}\mu\leq
c_{1}$. It also follows that $\mathsf{d}_{G}(v,f(v))=w(vf(v))\leq
c_{4}\cdot|\lambda(v)f(v)|\leq c_{4}\cdot\sqrt{2}\mu=\mathcal{O}(\mu)$.

Next, we define the edges of $H$. Consider two gridcells $C_{1}$ and $C_{2}$
with their special points $p_{1}$ and $p_{2}$, respectively. We add the edge
$p_{1}p_{2}$ to $H$ if $C_{1}$ and $C_{2}$ contain two points that are
neighbors in $G$. Thus, the maximum distance between two special points that
can contain an edge is at most $c_{2}+\mathcal{O}(\mu)$. As we pick at most
one special point from each grid cell, it follows that the degree of any
special point in $H$ is bounded by $\mathcal{O}(1/\mu^{2})$. Now, consider any
path $u_{1},u_{2},\ldots,u_{t}$ of $G$. Then the edge between two special
points $f(u_{i})$ and $f(u_{i+1})$ exists in $H$ for $1\leq i\leq t-1$. Hence,
the path $f(u_{1}),f(u_{2}),\ldots,f(u_{t})$ is in $H$. ∎

In the following analysis, we will often need the following generalization of
triangle inequality that works for powers of distances.

######  Lemma 1 (Triangle Inequality for Powers [39]).

Let $\epsilon>0$ and $z\geq 1$.

  1. 1.

For any non-negative reals $x,y$,
$(x+y)^{z}\leq(1+\epsilon)^{z-1}x^{z}+\left(\frac{1+\epsilon}{\epsilon}\right)^{z-1}y^{z}.$

  2. 2.

Let $(\Omega,\mathsf{d})$ be a metric space, and $u,v,w\in\Omega$, then,

$\mathsf{d}(u,v)^{z}\leq(1+\epsilon)^{z-1}\cdot(\mathsf{d}(u,v))^{z}+\left(\frac{1+\epsilon}{\epsilon}\right)^{z-1}(\mathsf{d}(v,w))^{z}.$

To prove the centroid set theorem, we show an explicit construction of a
centroid set. Recall that, due to the first canonical property, points in $V$
that are close to each other behaves as in the Euclidean case. To take care of
the case of points nearby to their closest centers, we add a set of points
$\mathbb{C}_{\text{net}}$ to our centroid set. The case of far away points is
further divided into two subcases. In the first subcase, we deal with the
points whose shortest paths to closest centers are short or $O(1/\epsilon)$
hops away. To take care of this subcase, we add a set of points
$\mathbb{C}_{\text{support}}$ to our centroid set. The last subcase concerns
long paths, and here we make use of the planar spanner property. In
particular, we construct the centroid points in this case based on a recursive
decomposition of the graph guided by underlying planar spanners of the
decomposed subgraphs. This subcase resembles the centroid set construction in
excluded-minor graph metrics from [18, 9].

Next, we proceed towards the details of our construction. But, before we
describe our approach, we need to define some ingredients, mainly to make
sense of the decomposition of a graph guided by planar spanners.

###  3.2 Shortest Path Separators and Recursive Decomposition

######  Proposition 5 ([31, 11]).

Given a planar graph $H=(V,E)$, with non-negative weights on vertices, there
exists a collection of shortest paths
$\mathcal{P}=\\{P_{1},P_{2},\ldots,P_{b}\\}$ with $b=\mathcal{O}(1)$, such
that the weight of the set of vertices belonging to any connected component in
$H\setminus\bigcup_{P_{i}\in\mathcal{P}}V(P_{i})$ has weight at most half of
that of $V(H)$.

Let $X\subseteq V(G)$ be a set of vertices, and let $I_{X}:V(G)\to\\{0,1\\}$
be the indicator function for $X$. We obtain a recursive decomposition
$\mathcal{T}=(\mathcal{R},E(\mathcal{T}))$ as follows, where every node of the
tree $R_{i}\in\mathcal{R}$ corresponds to a subset of $V(G)$, which is termed
as a region.

  * •

The region $R_{1}$ corresponding to the root of $\mathcal{T}$ is equal to
$V(G)$.

  * •

Consider an internal node of $\mathcal{T}$ that corresponds to a region
$R_{i}\subseteq V(G)$, such that $|R_{i}\cap X|>2$. Then, let
$G_{i}=G[R_{i}]$, and let $H_{i}$ be a planar $\alpha$-spanner for $G_{i}$.
Then, we apply Proposition 5 on $H_{i}$ to obtain a collection of
$\mathcal{O}(1)$ _separator paths_ $\mathcal{P}_{i}$, such that each
$P^{i,j}\in\mathcal{P}_{i}$ is a shortest path in $H_{i}$ w.r.t. $I_{X}$ being
the weight function (i.e., we seek to obtain a decomposition of the vertices
of $X$ in a balanced manner). Then, the regions that become the children of
$R_{i}$ in $\mathcal{T}$ are as follows. (See Figure 3 for an illustration)

    1. 1.

The subsets of vertices corresponding to the connected components in the
induced subgraph of $H_{i}$ on
$R_{i}\setminus\bigcup_{P^{i}_{j}\in\mathcal{P}_{i}}V(P^{i}_{j})$, and these
are termed as _component children_ of $R_{i}$ and

    2. 2.

Each path in $\mathcal{P}_{i}$ is broken into maximal sub-paths each
containing at most two points of $X$.222More precisely, if a path $P$ contains
at least one vertex of $X$, then interpret as a real interval $[0,1]$ with
break-points $0\leq x_{1}\leq x_{2}\leq\ldots\leq x_{m}\leq 1$, where
$x_{i}$’s are the vertices in $P\cap X$. Then, the sub-paths are given by
$[0,x_{1}],[x_{1},x_{2}],\ldots,[x_{m},1]$. If $P$ does not contain a vertex
of $X$, then let $P$ itself be the sub-path. Then, the vertex sets of each
such sub-paths are added as different children of $R_{i}$. These are termed as
_subpath children_.

Thus, a region $R_{i}$ is equal to the union of all the regions corresponding
to its component and subpath children. Note that only the regions
corresponding to the consecutive subpath children of a separator path may
intersect at a vertex of $X$; whereas the regions corresponding to the
component children of $R_{i}$ define a partition of
$R_{i}\setminus\bigcup_{P^{i,j}\in\mathcal{P}_{i}}V(P^{i}_{j})$.

  * •

Recursion stops when a region contains at most $2$ vertices of $X$, and such a
region is called a leaf region/node. Since the weight falls by a factor of at
least $1/2$ at every level, the height of $\mathcal{T}$ is at most
$\mathcal{O}(\log|X|)$.

Figure 3: Decomposition of a region $R_{i}$ into multiple children. Inside
$R_{i}$, we show the induced subgraph $G_{i}=G[R_{i}]$ (which is not planar)
and the corresponding planar spanner $H_{i}$. The edges of $H_{i}$ are shown
in red, and the edges in $E(G_{i})\setminus E(H_{i})$ are in black. The two
shortest-path separators of $H_{i}$ are shown in blue, which form a balanced
separator $\mathcal{P}_{i}$ for the vertices of $X$ (shown as light blue
squares). Then, we add a child for every connected component of $H\setminus
V(\mathcal{P}_{i})$ (children regions inside solid ellipses). We also have
children corresponding to paths in $\mathcal{P}_{i}$ (dashed ellipses). One of
the paths is broken into two pieces due to a vertex in $X$.

Fix a vertex $s\in V(G)$, and let $R_{1},R_{2},\ldots,R_{t}$ be the root-leaf
path in $\mathcal{T}$ such that $s$ is contained in every $R_{i}$, where
$R_{1}$ is the root region, and $R_{t}$ is a leaf region (recall that
$t=\mathcal{O}(\log|X|)$). Now consider any $p\in X\subseteq V(G)$. Let
$R_{i}$ be the lowest (i.e., one with the maximum $i$) region that contains
every vertex on a shortest path $\pi_{G}(p,s)$ in $G$ between $p$ and $s$.
Additionally, suppose $R_{i}$ is not equal to $R_{t}$. Then, the construction
implies that there exist two children $R_{i+1},R^{\prime}_{i+1}$ of $R_{i}$,
such that $p\in R^{\prime}_{i+1}$ and $s\in R_{i+1}$. Let $u$ be the _last
vertex_ along $\pi_{G}(p,s)$ (while going from $p$ to $s$) that lies in
$R^{\prime}_{i+1}$, and $v$ be the vertex immediately after $u$ along
$\pi_{G}(p,s)$. Note that $u,v$ belong to $R_{i}$, which induces a connected
component in $H_{i}$, and thus in $G_{i}$. Let $\pi_{H_{i}}(u,v)$ be a
shortest path between $u$ and $v$ in $H_{i}$. Since $u\in R^{\prime}_{i+1}$,
and $v\not\in R^{\prime}_{i+1}$, it follows that $\pi_{H_{i}}(u,v)$ intersects
with a path separator $P^{i,j}\in\mathcal{P}_{i}$ at a vertex $x$, such that
$x\in V(P^{i,j})\cap V(\pi_{H_{i}}(u,v))$. In this case, we say that $P^{i,j}$
_separates_ $p$ and $s$, and $x$ is a separating vertex that lies between $u$
and $v$ (see Figure 4). We summarize a few properties in the following
discussion.

Figure 4: A shortest path $\pi_{G}(p,s)$ is depicted on the right. On the left
hand side, we depict a path $P^{i,j}$ separating $p$ and $s$ and $x$ is a
separating vertex that lies between $u$ and $v$. Note that the paths
($P^{i,j}$) inside $R_{i}$ are shortest paths in the planar spanner $H_{i}$.
Also note that $u\in R^{\prime}_{i+1}$, and $s\in R_{i+1}$ by definition, but
$v$ may not belong to $R_{i+1}$.

######  Claim 2.

Let $P^{i,j}\in\mathcal{P}_{i}$ be a separator path corresponding to a region
$R_{i}$ that is the lowest region containing a shortest path $\pi(s,p)$, such
that $P^{i,j}$ separates $p$ and $s$, and $x$ is a separating vertex that lies
between $u$ and $v$. Then,

  1. 1.

$\mathsf{d}_{G_{i}}(p,s)=\mathsf{d}_{G}(p,s)$,

  2. 2.

$\mathsf{d}_{G_{i}}(u,v)\leq\mathsf{d}_{H_{i}}(u,v)\leq\alpha\cdot\mathsf{d}_{G_{i}}(u,v)=\alpha\cdot\mathsf{d}_{G}(u,v)$,

  3. 3.

$\mathsf{d}_{H_{i}}(u,x)+\mathsf{d}_{H_{i}}(v,x)=\mathsf{d}_{H_{i}}(u,v)\leq\alpha\cdot\mathsf{d}_{G_{i}}(u,v)=\alpha\cdot\mathsf{d}_{G}(u,v)$

  4. 4.

For any $q>0$, if $|\pi_{G}(p,s)|\geq q\cdot\frac{\alpha\cdot
c^{\prime}_{2}}{c^{\prime}_{1}\cdot\epsilon}$, then
$\mathsf{d}_{H_{i}}(u,v)\leq\epsilon/q\cdot\mathsf{d}_{G}(p,s)$.

###### Proof.

The first property follows from the assumption that $R_{i}$ contains all the
vertices along the shortest path $\pi_{G}(p,s)$, thus $G_{i}=G[R_{i}]$ also
contains the shortest path $\pi_{G}(p,s)$. Now consider the second property.
Note that $u$ and $v$ are consecutive vertices along $\pi_{G}(p,s)$, which is
a shortest path in $G$ and $G_{i}$. Thus, there exists a shortest path
$\pi_{H_{i}}(u,v)$ in $H_{i}$, which is an $\alpha$-spanner for $G_{i}$, of
weight at most $\alpha$ times $\mathsf{d}_{G_{i}}(u,v)$. For the third
inequality, recall that $x$ is a vertex along the path $\pi_{H_{i}}(u,v)$, and
then we use the second item.

Since $\pi_{G}(p,s)$ contains at least $q\cdot\frac{\alpha
c^{\prime}_{2}}{\epsilon c^{\prime}_{1}}$ vertices, the Bounded Distance
property of $G$ implies that, $\mathsf{d}_{G}(p,s)\geq c^{\prime}_{1}\cdot
q\frac{\alpha c^{\prime}_{2}}{\epsilon c^{\prime}_{1}}=q\cdot\frac{\alpha
c^{\prime}_{2}}{\epsilon}$, whereas $\mathsf{d}_{G}(u,v)\leq c^{\prime}_{2}$.
Then, it follows that
$\mathsf{d}_{H_{i}}(u,v)\leq\alpha\cdot\mathsf{d}_{G}(u,v)\leq\alpha
c^{\prime}_{2}\leq\frac{\epsilon}{q}\cdot\mathsf{d}_{G}(p,s)$. ∎

Note that the last item in the above claim infers that the distance between
$u$ and $v$ in the spanner $H_{i}$ is negligible if $|\pi_{G}(p,s)|$ is large
enough.

###  3.3 Construction of the Centroid Set

We will construct the three sets of centers
$\mathbb{C}_{\text{landmark}},\mathbb{C}_{\text{support}},$ and
$\mathbb{C}_{\text{net}}$, and define the centroid set as the union of the
three sets, i.e.,
$\mathbb{C}\coloneqq\mathbb{C}_{\text{landmark}}\cup\mathbb{C}_{\text{support}}\cup\mathbb{C}_{\text{net}}$.
The three sets correspond to the three cases we discussed before.

###### Nearby points case.

First, we construct the set $\mathbb{C}_{\text{net}}$. Let
$p_{1},p_{2},\ldots,p_{n^{\prime}}$ be the points of $X$ such that
$\mathsf{d}_{G}(p,\mathcal{A})<1$ for all $p=p_{i}$, where $1\leq i\leq
n^{\prime}$. Let
$B_{i}=B(p_{i},(10z/\epsilon)\cdot\mathsf{d}_{G}(p_{i},\mathcal{A}))$ be the
set of points contained within distance
$10z/\epsilon\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})$ from $p_{i}$. Then, we
use Proposition 3 to compute a set $B^{\prime}_{i}\subseteq B_{i}$ by setting
$\mu=\Theta(\epsilon^{3}/z^{3})\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})$, and
add all points of every such $B^{\prime}_{i}$ to $\mathbb{C}_{\text{net}}$.

###### Short-path case.

Next, we construct the set $\mathbb{C}_{\text{support}}$. Consider the Bounded
Degree Support Graph $H^{\prime\prime}=(V^{\prime\prime},E^{\prime\prime})$
obtained by applying Proposition 4 with precision value
$\mu=\epsilon^{2}/z^{2}$. Also consider the mapping $f:V(G)\rightarrow
V(H^{\prime\prime})$. For each point $p\in X$, add any vertex $v\in
V(H^{\prime\prime})$ to $\mathbb{C}_{\text{support}}$ that is at most
$\ell=\frac{\gamma\cdot z\alpha\cdot
c^{\prime}_{2}}{c^{\prime}_{1}\cdot\epsilon}$ hops away from $f(p)$ in
$H^{\prime\prime}$, i.e., there is a path between $v$ and $f(p)$ in
$H^{\prime\prime}$ containing at most $\ell$ edges. Here, $\gamma\geq 1$ is a
large enough constant (it suffices to set $\gamma=1600$).

###### Long-path case.

First, we define a set of important points, referred to as the landmarks,
which will help us divide the points of $V$ into equivalence classes. In
particular, each equivalence class would contain a subset of points of $V$
whose distance vectors w.r.t. a fixed sequence of landmarks are approximately
equal. Moreover, the centroid set we will construct contains exactly one
representative point from each such equivalence class, essentially leading to
a small-sized set. To this end, we will then define a notion of _rounded
distances_ to landmarks, and use it to construct
$\mathbb{C}_{\text{landmark}}$ such that for each possible distance tuple,
$\mathbb{C}_{\text{landmark}}$ contains a point having that _rounded_ distance
tuple.

Landmarks. Let $0\leq\mu\leq\frac{1}{2}$ be small enough – later we will
define $\mu$ to be a function of $\epsilon$ and $z$. Throughout the following
discussion, fix a root-leaf path $R_{1},R_{2},\ldots,R_{t}$ in $\mathcal{T}$,
where $R_{1}$ is the root region, and $R_{t}$ is a leaf-region. Without loss
of generality, we assume that $R_{t}\cap X\neq\emptyset$ – otherwise we prune
such a root-leaf path at the lowest region that contains at least one vertex
of $X$. Note that $t=\mathcal{O}(\log|X|)$. We recall some notation from
Section 3.2. Let $G_{i}=G[R_{i}]$ be an induced subgraph corresponding to
region $R_{i}$, and let $H_{i}$ be a constant-stretch spanner of $G_{i}$. For
$1\leq i\leq t-1$, let $\mathcal{P}_{i}$ be the set of shortest-path
separators obtained by applying Proposition 5 to obtain the children of
$R_{i}$ in the recursive decomposition, where
$\mathcal{P}_{i}=\\{P^{i,1},P^{i,2},\ldots,P^{i,b}\\}$, with
$b=\mathcal{O}(1)$. Let $\mathcal{P}=\bigcup_{i=1}^{t-1}\mathcal{P}_{i}$.
Finally, we define some notational shorthand: let
$d_{i}(\cdot,\cdot)=d_{G_{i}}(\cdot,\cdot)$, and
$\mathsf{d}(\cdot,\cdot)=d_{G}(\cdot,\cdot)$. For a path $P^{i,j}$, and a
point $q_{1}\in X$, we consider two ways of defining rounded distance tuples,
that will be useful in different cases.

First rounded distance tuple. Consider a non-leaf region $R_{i}$ and a
shortest path $P^{i,j}\in\mathcal{P}_{i}$. For every pair of vertices
$q_{1},q_{2}\in X$, let
$D(i,q_{1},q_{2})\coloneqq\mathsf{d}_{i}(q_{1},q_{2})+\mathsf{d}(q_{2},\mathcal{A})$.
We fix $i$ and points $q_{1},q_{2}$ until the end of the current discussion
about first rounded distance tuple, and use $D\coloneqq D(i,q_{1},q_{2})$ for
brevity.

Let $Q^{i,j}(q_{1},q_{2})$ denote the set of vertices $v$ on the path
$P^{i,j}$ such that $\mathsf{d}_{i}(v,q_{1})\leq D/\mu^{2}$. Arbitrarily
orienting $P^{i,j}$ from one endpoint to another, let $u$ and $v$ denote the
first and last vertex belonging to $Q^{i,j}$ respectively. Note that,

$\displaystyle\mathsf{d}_{P^{i,j}}(u,v)$
$\displaystyle=\mathsf{d}_{H_{i}}(u,v)$ (Since $P^{i,j}$ is a shortest path in
$H_{i}$)
$\displaystyle\leq\mathsf{d}_{H_{i}}(u,q_{1})+\mathsf{d}_{H_{i}}(q_{1},v)$
$\displaystyle\leq\alpha\cdot\left(\mathsf{d}_{i}(u,q_{1})+\mathsf{d}_{i}(q_{1},v)\right)$
$\displaystyle\leq\frac{2\alpha D}{\mu^{2}}.$

Now, we construct an $(\mu^{2}\cdot D)$-net $\mathcal{L}(i,j,q_{1},q_{2})$ of
$Q^{i,j}(q_{1},q_{2})$. Formally, we treat the subpath between $u$ and $v$ as
a real interval $\left[0,\beta\right]$, where $\beta\leq\frac{2\alpha
D}{\mu^{2}}$. We place a ``mark'' at every $\mu^{2}D$ units of distance. Now
we go back to the subpath, which is a discrete sequence of edges. If a mark
coincides with a vertex along the path, then we add the vertex to the set
$\mathcal{L}(i,j,q^{i,j})$. Otherwise, if a mark falls between two consecutive
vertices along the path, then we add both of the vertices to the set
$\mathcal{L}(i,j,q_{1},q_{2})$.

######  Observation 1.

  * •

$|\mathcal{L}(i,j,q_{1},q_{2})|=\mathcal{O}\left(\mu^{-4}\right)$ (since
$\alpha$ is an absolute constant), and

  * •

For any $x\in V(P^{i,j})$ with $\mathsf{d}_{G_{i}}(q_{1},x)\leq D/\mu^{2}$,
there exists an $l\in\mathcal{L}(i,j,q_{1},q_{2})$ such that
$\mathsf{d}_{G_{i}}(x,l)\leq\mathsf{d}_{H_{i}}(x,l)=\mathsf{d}_{P^{i,j}}(x,l)\leq\mu^{2}D$.

Let $R^{\prime}_{t}=\left\\{s\in R_{t}:|\pi_{G}(x,s)|>\ell\text{ for all }x\in
X\right\\}$. That is, $R^{\prime}_{t}$ is the subset of $R^{\prime}_{t}$ of
points $s$ such that the hop-distance of $s$ from _every point in $X$_ along
the shortest path in $G$, is strictly larger than $\ell$.

For a path $P^{i,j}\in\mathcal{P}_{i}$, for each $q_{1},q_{2}\in X$, and any
point $s\in R^{\prime}_{t}\subseteq R_{t}$, we consider the following _rounded
distance tuple_ $\tilde{\mathsf{d}}^{1}_{i,j}(s,(q_{1},q_{2}))$, defined as
the tuple formed by listing the following entries in a fixed order:

  * •

For each $l\in\mathcal{L}(i,j,q_{1},q_{2})$:
$\displaystyle\tilde{d}^{1}_{i,j}(s,l)=\min\left\\{\left\lceil\frac{\mathsf{d}_{i}(s,l)}{\mu^{2}D}\right\rfloor,\frac{3D}{\mu^{2}}\right\\}$.

  * •

$\displaystyle\tilde{d}^{1}_{i,j}(s,q_{1})=\left\\{\left\lceil\frac{\mathsf{d}_{i}(s,q_{1})}{\mu
D}\right\rfloor,\frac{3D}{\mu}\right\\}$.

  * •

For each $x\in X\cap R_{t}$:
$\tilde{d}^{1}_{i,j}(s,x)=\left\\{\left\lceil\frac{\mathsf{d}_{i}(x,s)}{\mu\mathsf{d}(x,\mathcal{A})}\right\rfloor,\frac{1}{\mu}\mathsf{d}(x,\mathcal{A})\right\\}$.

Here, we use the notation $\lceil\frac{p}{q}\rfloor$ to denote the integral
multiple of $q$ that is closest to $\frac{p}{q}$.

For a leaf region $R_{t}$, there are no corresponding shortest path
separators. Thus, we consider a different definition first rounded distance
tuple. Let $\mathcal{L}(t)=R_{t}\cap X$. For each $p\in\mathcal{L}(t)$, let
$\tilde{d}_{t}(s,x)=\left\\{\left\lceil\frac{\mathsf{d}(x,s)}{\mu\mathsf{d}(x,\mathcal{A})}\right\rfloor,\frac{1}{\mu}\mathsf{d}(x,\mathcal{A})\right\\}$.
Let $\tilde{\mathsf{d}}^{1}_{t}(s,t)$ be this tuple.

Second rounded distance tuple. Again, fix a path $P^{i,j}\in\mathcal{P}_{i}$,
and a point $q_{1}\in X$, and a pair $q_{3},q_{4}\in R_{i}\cup\\{\bot\\}$,
where $\bot$ means undefined. Furthermore, we assume that $q_{3}$ and $q_{4}$
both are not undefined at the same time. Then, for a point $s\in
R^{\prime}_{t}\subseteq R_{t}$, we define the second rounded distance tuple
$\tilde{d}^{2}_{i,j}(s,(q_{1},q_{3},q_{4}))$, defined as follows.

  * •

$\tilde{d}^{2}_{i,j}(s,(q_{1},q_{3},q_{4}))=\texttt{true}$ if

$\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q_{1},q_{4})+\mathsf{d}(q_{4},\mathcal{A})\right)<\mathsf{d}_{i}(q_{1},s)<\mu\cdot\left(\mathsf{d}_{i}(q_{1},q_{3})+\mathsf{d}(q_{3},\mathcal{A})\right)$

Here, if $q_{4}=\bot$, then the first inequality is omitted from the
definition, and if $q_{3}=\bot$, then the second inequality is omitted from
the definition. Note that due to our assumption, at least one of $q_{3}$ and
$q_{4}$ is not undefined, so the definition cannot be vacuously true.

  * •

$\tilde{d}^{2}_{i,j}(s,(q_{1},q_{3},q_{4}))=\texttt{false}$ otherwise, i.e.,
when $q_{4}\neq\bot$ and the first inequality does not hold, or when
$q_{3}\neq\bot$ and the second inequality does not hold.

Construction of $\mathbb{C}_{\text{landmark}}$.  For each root-leaf path
$R_{1},\ldots,R_{t}$, for each $P^{i,j}\in\mathcal{P}$, and we of the two
choices of rounding of distances (i.e., $\tilde{d}^{1}_{i,j}(\cdot,\cdot)$ or
$\tilde{d}^{2}_{i,j}(\cdot,\cdot)$), we consider all possible values that the
entries in the corresponding rounded tuples may take. We also consider the
rounded distance tuple $\tilde{\mathsf{d}}^{1}_{t}(\cdot)$. For each possible
choice of rounding type and of the entries, we obtain a large rounded distance
tuple $\tilde{\mathsf{D}}$ by concatenating all tuples thus constructed in a
fixed order. That is, $\tilde{\mathsf{D}}$ is obtained by corresponding
rounded distance tuples (i.e., either the potential numerical or true/false
values that the entries in $\tilde{d}^{1}_{\cdot}(\cdot)$ or
$\tilde{d}^{2}_{\cdot}(\cdot)$ may take respectively). If there exists a point
$s\in R^{\prime}_{t}\subseteq R_{t}$ that achieves all the corresponding
entries (i.e., rounded distance values and/or true/false), as specified by
$\tilde{\mathsf{D}}$, then we add it to $\mathbb{C}_{\text{landmark}}$.

###  3.4 Construction of the Approximate Solution

We now show that for any solution $\mathcal{S}$, every center in $\mathcal{S}$
can be approximated by a centroid from $\mathbb{C}$. Consider any center
$s\in\mathcal{S}$, and let $X_{s}\subseteq X$ be the subset of points whose
closest center in $S$ is $s$ (breaking ties arbitrarily). First, we show how
to find $\tilde{s}\in\mathbb{C}$ such that for any point $p\in X_{s}$ with
$\mathsf{cost}(p,s)\leq\left(\frac{10z}{\epsilon}\right)^{z}\cdot\mathsf{cost}(p,\mathcal{A})$,
$\mathsf{cost}(p,\tilde{s})\leq\mathsf{cost}(p,s)+3\epsilon\left(\mathsf{cost}(p,s)+\mathsf{cost}(p,\mathcal{A})\right)$.

Now, we show how to find a replacement center for any $s\in\mathcal{S}$, which
we denote by $\rho(s)$. We consider different cases to find $\rho(s)$. The
following cases, or _replacement rules_ , are applied in the following manner.
We proceed to each of the replacement rules in the order in which they are
presented. For a particular replacement rule, we iterate over all centers
$s\in\mathcal{S}$ for which replacement has not yet been found using previous
rules, and check whether the current rule is applicable to $s$, in which case
we define $\rho(s)$ as specified by the rule. Thus, at the end of the
iteration, we are left with the centers $s\in\mathcal{S}$ for which none of
the previous rules are applicable. Then, we proceed to the next rule and
proceed in a similar manner.

Replacement using $\mathbb{C}_{\text{net}}$.

Case 1. Suppose there exists a point $p\in X_{s}$ with
$\mathsf{d}_{G}(p,\mathcal{A})<1$.
Let $X^{\prime}_{s}\coloneqq\\{q\in X_{s}:\mathsf{d}_{G}(q,\mathcal{A})<1\\}$.
Note that $p\in X^{\prime}_{s}$, which implies that
$X^{\prime}_{s}\neq\emptyset$. Let
$p_{i}\coloneqq\operatorname*{arg\,min}_{\\{q\in
X^{\prime}_{s}\\}}\mathsf{d}_{G}(q,\mathcal{A})+\mathsf{d}_{G}(q,s)$. Note
that $s\in
B_{i}=B(p_{i},(10z/\epsilon)\cdot\mathsf{d}_{G}(p_{i},\mathcal{A}))$. Let
$\tilde{s}$ be the closest point to $s$ in the
$(\epsilon^{3}/z^{3})\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})$-net
$B^{\prime}_{i}$ constructed for $B_{i}$. Note that such an $\tilde{s}$ was
added to $\mathbb{C}_{\text{net}}$. In this case, we add
$\tilde{s}\in\mathbb{C}_{\text{net}}\subseteq\mathbb{C}$ to
$\tilde{\mathcal{S}}$, and set $\rho(s)=\tilde{s}\in\mathbb{C}_{\text{net}}$.
Define $\mathcal{S}_{\text{net}}$ as the subset of $\mathcal{S}$ as all the
centers $s$ whose replacement was found using this manner.

Case 2. Consider the following case.

  1. 1.

Suppose for all points $p\in X_{s}$, it holds that
$\mathsf{d}_{G}(p,\mathcal{A})\geq 1$, and thus, we have not found $\rho(s)$
in the previous case,

  2. 2.

$f(s)\in V(H^{\prime\prime})$ was added to
$\mathbb{C}_{\text{support}}\subseteq\mathbb{C}$, and

  3. 3.

There exists a point $q\in X_{s_{q}}$ where $s\neq
s_{q}\in\mathcal{S}_{\text{net}}$, and
$\tilde{s}_{q}=\rho(s_{q})\in\mathbb{C}_{\text{net}}$ with the following
properties: (1) $\mathsf{d}_{G}(q,s_{q})\leq\epsilon/z$, (2)
$\mathsf{d}_{G}(q,\tilde{s}_{q})>\mathsf{d}_{G}(q,f(s))$.

In this case, we let $\rho(s)=\tilde{s}_{q}$, as defined above (if there are
multiple choices for $q$, and thus for $s_{q}$, we may choose arbitrarily). We
define $\mathcal{S}_{\text{net-sub}}$ as the subset of $\mathcal{S}$ as all
the centers $s$ whose replacement was found using this case. Note that for
centers $s$ in $\mathcal{S}_{\text{net}}$ as well as $\mathcal{S}_{\text{net-
sub}}$, $\rho(s)$ belongs to $\mathbb{C}_{\text{net}}$; but the difference is
that, for a center $s\in\mathcal{S}_{\text{net-sub}}$, we make use of a center
in $\tilde{\mathcal{S}}$ that was already found as a replacement for a
_different_ center $s_{q}\in\mathcal{S}_{\text{net}}$.

Replacement using $\mathbb{C}_{\text{support}}$. Consider the case when the
first two items in the previous case hold, but there is no point $p$
satisfying the conditions in the third item. That is, suppose $s$ satisfies
the following conditions:

  1. 1.

Suppose for all points $q\in X_{s}$, it holds that
$\mathsf{d}_{G}(q,\mathcal{A})\geq 1$,

  2. 2.

$f(s)\in V(H^{\prime\prime})$ was added to
$\mathbb{C}_{\text{support}}\subseteq\mathbb{C}$, and

  3. 3.

There exists no point $p\in X_{s_{p}}$ where $s\neq s_{p}\in\mathcal{S}$, and
$s^{\prime}_{p}=\rho(s_{p})\in\mathbb{C}_{\text{net}}$ with the following
properties: (1) $\mathsf{d}_{G}(p,s_{p})\leq\epsilon/z$, and (2)
$\mathsf{d}_{G}(p,s^{\prime}_{p})>\mathsf{d}_{G}(p,f(s))$.

Then, we add $f(s)$ to $\tilde{\mathcal{S}}$, and set $\rho(s)=f(s)$. Let
$\mathcal{S}_{\text{support}}\subseteq\mathcal{S}$ denote the set of centers
$s$ such that $\rho(s)\in\mathbb{C}_{\text{support}}$.

We let
$\mathcal{S}_{\text{landmark}}\coloneqq\mathcal{S}\setminus(\mathcal{S}_{\text{net}}\cup\mathcal{S}_{\text{net-
sub}}\cup\mathcal{S}_{\text{support}})$ denote the subset of centers whose
replacement has not been found in either $\mathbb{C}_{\text{net}}$ or in
$\mathbb{C}_{\text{support}}$ as specified in the previous paragraph. Here,
the notation anticipates that for such centers
$s\in\mathcal{S}_{\text{landmark}}$, we will find $\rho(s)$ using
$\mathbb{C}_{\text{landmark}}$. Before that, we first note the following
observation.

######  Observation 2.

For any $s\in\mathcal{S}_{\text{landmark}}$ and for any point $p\in X$,
$|\pi_{G}(p,s)|>\ell$.

###### Proof.

Suppose for contradiction that for some $s\in\mathcal{S}_{\text{landmark}}$
and $p\in X$ $p,u_{1},\ldots,u_{t},s$ is a path $\pi_{G}(p,s)$. Then the path
$f(p),f(u_{1}),\ldots,f(u_{t}),f(s)$ is in $H^{\prime\prime}$. Thus, $f(s)$ is
at most $\ell$ hops away from $f(p)$, and hence $f(s)$ should have been added
to $\mathbb{C}$ by our construction. But, this is a contradiction, and hence
$|\pi_{G}(p,s)|>\ell$. ∎

Replacement using $\mathbb{C}_{\text{landmark}}$. Now, we show how to find a
replacement for $s\in\mathcal{S}_{\text{landmark}}$ using
$\mathbb{C}_{\text{landmark}}$. For this, we make use of the recursive
decomposition tree $\mathcal{T}$ and the set $\mathbb{C}_{\text{landmark}}$
constructed previously. Fix the center $s\in\mathcal{S}_{\text{landmark}}$ for
the following discussion, and let $R_{t}$ be the leaf node of $\mathcal{T}$
containing $s$. Let $\Pi=(R_{1},R_{2},\ldots,R_{t})$. Note that 2 implies that
$s\in R^{\prime}_{t}\subseteq R_{t}$.

Consider a non-leaf region $R_{i}$, and a path $P^{i,j}\in\mathcal{P}_{i}$.
Again, we use the shorthand $\mathsf{d}_{i}=\mathsf{d}_{G_{i}}$, and
$\mathsf{d}=\mathsf{d}_{G}$. Recall that $G_{i}=G[R_{i}]$. Let
$q^{i}_{1}=\arg\min_{p\in R_{i}}\mathsf{d}_{i}(p,s)$. Now, we consider two
cases.

  1. 1.

There exists some $q^{i}_{2}\in R_{i}$ such that
$\mu\mathsf{d}_{i}(q^{i}_{1},s)\leq\mathsf{d}_{i}(q^{i}_{1},q^{i}_{2})+\mathsf{d}(q^{i}_{2},\mathcal{A})\leq\frac{1}{\mu}\mathsf{d}_{i}(q^{i}_{2},s)$.
In this case, we pick the rounding
$\tilde{\mathsf{d}}^{1}_{i,j}(s,(q^{i}_{1},q^{i}_{2}))$.

  2. 2.

Otherwise, we proceed as follows.
(i) If there exists a point $q\in R_{i}$ such that (i)
$\mathsf{d}_{i}(q^{i}_{1},q)+\mathsf{d}(q,\mathcal{A})>\frac{1}{\mu}\mathsf{d}_{i}(q^{i}_{1},s)$.
Then, let $q^{i}_{3}=\arg\min_{q\in
R_{i}}\mathsf{d}_{i}(q^{i}_{1},q)+\mathsf{d}(q,\mathcal{A})$. If there exists
no such $q\in R_{i}$, then let $q^{i}_{3}=\bot$, i.e., undefined.
(ii) If there exists a point $q\in R_{i}$ such that (i)
$\mathsf{d}_{i}(q^{i}_{1},q)+\mathsf{d}(q,\mathcal{A})<\mu\mathsf{d}_{i}(q^{i}_{1},s)$.
Then, let $q^{i}_{4}=\arg\max_{q\in
R_{i}}\mathsf{d}_{i}(q^{i}_{1},q)+\mathsf{d}(q,\mathcal{A})$. If there exists
no such $q\in R_{i}$, then let $q^{i}_{4}=\bot$, i.e., undefined.
Note that at least one of $q^{i}_{3}$ and $q^{i}_{4}$ is not undefined. In
this case, we pick the rounding
$\tilde{\mathsf{d}}^{2}_{i,j}(s,(q^{i}_{1},q^{i}_{3},q^{i}_{4}))$.

We obtain a rounded distance tuple $\tilde{\mathsf{D}}(s)$ by concatenating
over all paths $P^{i,j}\in\mathcal{P}$, the rounded distance tuples
$\tilde{d}^{1}_{i,j}(s,\cdot)$, or $\tilde{d}^{2}_{i,j}(s,\cdot)$ as defined
above. Since $s\in R^{\prime}_{t}$ and has the rounded distance tuple
$\tilde{\mathsf{D}}(s)$, we conclude that $\mathbb{C}_{\text{landmark}}\cap
R^{\prime}_{t}$ must contain a point, say $\tilde{s}$, that also has the
rounded distance tuple $\tilde{\mathsf{D}}(s)$. We let $\rho(s)=\tilde{s}$.

This completes the construction of the set
$\tilde{\mathcal{S}}\subseteq\mathbb{C}$. In the next subsection, we analyze
the properties of this solution.

###  3.5 Error Analysis

In this section, we show how to bound the error for any relevant point $p\in
X_{s}$. The overarching goal is to show that, for any point $p\in X$ such that
$\mathsf{d}_{G}(p,\mathcal{S})\leq\frac{\gamma^{\prime}z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$,
or
$\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\frac{\gamma^{\prime}z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$,
it holds that
$|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|\leq\mathcal{O}(\epsilon)\cdot(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A}))$.
Since we the set $\tilde{\mathcal{S}}$ is constructed by careful examination
of different cases, the proof of this claim is also based on exhaustive case
analysis, which is organized into different lemmas. Before we proceed to
formally state and prove these lemmas, we start with a high-level overview of
the conceptual flow of the argument.

Forward direction. For a point $p\in X$ with $s$ being its closest center in
$\mathcal{S}$, we consider different cases based on whether $s$ belongs to
$\mathcal{S}_{\text{net}}$, $\mathcal{S}_{\text{support}}$, or
$\mathcal{S}_{\text{landmark}}$. This corresponds to 3, 4, 5, and Lemma 2,
respectively. Here, we show that for some $\mu\geq 0$, either
$\mathsf{d}_{G}(p,s)>\frac{\mu
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$, or
$\mathsf{d}_{G}(p,\rho(s))\leq(1+\epsilon/z)\cdot\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
This comprises of the forward direction of the proof.

Reverse direction. For a point $p\in X$ with $s\in\mathcal{S}$ and
$\tilde{s}\in\tilde{\mathcal{S}}$ being its closest centers in the two sets
respectively. If $\tilde{s}=\rho(s)$, then it is relatively straightforward to
argue that, if $\mathsf{d}_{G}(p,\tilde{s})\leq\frac{\mu
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$, then for some $\mu\geq 0$,
$\mathsf{d}_{G}(p,s)\leq(1+\epsilon/z)\cdot\mathsf{d}_{G}(p,\tilde{s})+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
In another case, we may have that $\tilde{s}=\rho(s^{\prime})$, where
$s^{\prime}\neq s$. That is, $\tilde{s}\in\tilde{\mathcal{S}}$ was found as a
replacement for a center $s^{\prime}$ that is _not_ the closest center in
$\tilde{\mathcal{S}}$ to the point $p$. Here, the subtle possibility is that
$\mathsf{d}_{G}(p,\tilde{s})\ll\mathsf{d}_{G}(p,s)$, in which case we cannot
hope to show the required bound. To argue that this does not happen, we
carefully examine the different cases used to find $\rho(s)$ and
$\rho(s^{\prime})$, the replacements for $s$ and $s^{\prime}$, respectively.
The reverse direction comprises of 6, 7 and Lemma 2.

Finally, we combine the two directions, and show the required error bound on
the solution in Lemma 4.

#### Forward Direction

######  Claim 3.

Consider a point $p\in X_{s}$ with $s\in\mathcal{S}_{\text{net}}$ with
$\mathsf{d}_{G}(p,s)\leq\frac{10z}{\epsilon}\mathsf{d}_{G}(p,\mathcal{A})$.
Then, for $\rho(s)=\tilde{s}\in\mathbb{C}_{\text{net}}$, it holds that
$|\mathsf{d}_{G}(p,\tilde{s})-\mathsf{d}_{G}(p,s)|\leq(\epsilon/z)\cdot(\mathsf{d}_{G}(p,s)+\mathsf{d}_{G}(p,\mathcal{A}))$.

###### Proof.

Since $s\in\mathcal{S}_{\text{net}}$, the set $X^{\prime}_{s}=\\{q\in
X_{s}:\mathsf{d}_{G}(q,\mathcal{A})<1\\}$ is non-empty. Then, we choose
$p_{i}=\operatorname*{arg\,min}_{q\in
X^{\prime}_{s}}\mathsf{d}_{G}(q,\mathcal{A})+\mathsf{d}_{G}(q,s)$. Note that
$s\in B_{i}=B(p_{i},(10z/\epsilon)\cdot\mathsf{d}_{G}(p_{i},\mathcal{A}))$,
and a point $\tilde{s}$ closest to $s$ from the
$(\epsilon^{3}/z^{3})\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})$-net of $B_{i}$ is
added to $\mathbb{C}_{\text{net}}$. Now,
$\mathsf{d}_{G}(s,\tilde{s})\leq(\epsilon^{3}/z^{3})\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})<(\epsilon/z)$.

Now, there are two possibilities. If $\mathsf{d}_{G}(p,\mathcal{A})\geq 1$,
then
$|\mathsf{d}_{G}(p,\tilde{s})-\mathsf{d}_{G}(p,s)|\leq\epsilon/z\leq(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

Otherwise, if $\mathsf{d}_{G}(p,\mathcal{A})<1$, then $p\in X^{\prime}_{s}$.
Therefore,
$\mathsf{d}_{G}(p_{i},s)+\mathsf{d}_{G}(p_{i},\mathcal{A})\leq\mathsf{d}_{G}(p,s)+\mathsf{d}_{G}(p,\mathcal{A})$.
Hence,
$|\mathsf{d}_{G}(p,\tilde{s})-\mathsf{d}_{G}(p,s)|\leq\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p_{i},\mathcal{A})\leq\frac{\epsilon}{z}(\mathsf{d}_{G}(p,s)+\mathsf{d}_{G}(p,\mathcal{A}))$.
∎

######  Claim 4.

Consider a point $p\in X_{s}$ for some $s\in\mathcal{S}_{\text{net-sub}}$,
such that
$\mathsf{d}_{G}(p,s)\leq\frac{10z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
Then,
$\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

###### Proof.

First, we claim that $\mathsf{d}_{G}(p,\mathcal{A})\geq 1$. Suppose for the
contradiction that $\mathsf{d}_{G}(p,\mathcal{A})<1$. Then, we would have
found a replacement for $s$ in $\mathbb{C}_{\text{net}}$ using Case 1, i.e.,
$s\in\mathcal{S}_{\text{net}}$. However, since $s\in\mathcal{S}_{\text{net-
sub}}$, Case 1 is not applicable, which is a contradiction.

Since $s\in\mathcal{S}_{\text{net-sub}}$, there exists a point
$f(s)\in\mathbb{C}_{\text{support}}$ such that
$\mathsf{d}_{G}(s,f(s))=\mathcal{O}(\epsilon^{2}/z^{2})$. Furthermore, there
exists a point $q\in X_{s_{q}}$ for some $s_{q}\in\mathcal{S}_{\text{net}}$
such that $\tilde{s}_{q}=\rho(s_{q})$ satisfies the following properties: (1)
$\mathsf{d}_{G}(q,s_{q})\leq\epsilon/z$, (2)
$\mathsf{d}_{G}(q,\tilde{s}_{q})>\mathsf{d}_{G}(q,f(s))$. Then,

$\displaystyle\mathsf{d}_{G}(p,\tilde{s}_{q})$
$\displaystyle\leq\mathsf{d}_{G}(p,s)+\mathsf{d}_{G}(s,f(s))+\mathsf{d}_{G}(f(s),q)+\mathsf{d}_{G}(q,\tilde{s}_{q})$
$\displaystyle\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})+2\cdot\mathsf{d}_{G}(q,\tilde{s}_{q})$
($\because\ \mathsf{d}_{G}(q,f(s))\leq\mathsf{d}_{G}(q,\tilde{s}_{q})$)
$\displaystyle\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})+2\cdot\left(\mathsf{d}_{G}(q,s_{q})+\mathsf{d}_{G}(s_{q},\tilde{s}_{q})\right)$
$\displaystyle\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})+2\cdot\epsilon/z$
($\because\ d(q,s_{q})\leq\epsilon/z$ and
$\mathsf{d}_{G}(s_{q},{s^{\prime}}_{q})\leq\epsilon^{3}/z^{3}$)
$\displaystyle\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$
($\because\ \mathsf{d}_{G}(p,\mathcal{A})\geq 1$. )

∎

######  Claim 5.

Consider a point $p\in X_{s}$ for some $s\in\mathcal{S}_{\text{support}}$ such
that
$\mathsf{d}_{G}(p,s)\leq\frac{10z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
Then,
$\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

###### Proof.

Arguing as in the proof of 4, we first observe that
$\mathsf{d}_{G}(p,\mathcal{A})\geq 1$, otherwise $s$ would belong to
$\mathcal{S}_{\text{net}}$, which is a contradiction. Since
$s\in\mathcal{S}_{\text{support}}$, $f(s)$ has been added to
$\mathbb{C}_{\text{support}}$, and we set $\rho(s)=f(s)$. Thus, $G$ has a path
between $p$ and $f(s)$ of length exactly $|\pi_{G}(p,s)|+1$ whose weight is
$\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})$, namely the path
obtained by appending the edge $\\{s,f(s)\\}$ with the path $\pi_{G}(p,s)$.
Hence,

$\mathsf{d}_{G}(p,f(s))\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})\leq\mathsf{d}_{G}(p,s)+\mathcal{O}(\epsilon^{2}/z^{2})\cdot\mathsf{d}_{G}(p,\mathcal{A})$

The last inequality follows, as $\mathsf{d}_{G}(p,\mathcal{A})\geq 1$. ∎

Now, consider a point $p\in X_{s}$ with
$\mathsf{d}_{G}(p,s)\leq\frac{10z}{\epsilon}\mathsf{d}_{G}(p,\mathcal{A})$.
Now, if none of the 3, 4, and 5 is applicable, then it follows that
$s\not\in(\mathcal{S}_{\text{net}}\cup\mathcal{S}_{\text{net-
sub}}\cup\mathcal{S}_{\text{support}})$. That is,
$s\in\mathcal{S}_{\text{landmark}}$. From 2, it follows that for all points
$q\in X$, the hop-length of the path $\pi_{G}(q,s)$, i.e., $|\pi_{G}(q,s)|$,
is strictly larger than $\ell$.

In the following lemma, we show that the replacement $\rho(s)$ fond for $s$
from the set $\mathbb{C}_{\text{landmark}}$ has approximately the same
distance to $p$ as $s$. In fact, the following lemma is stronger in the
following two aspects. First, it does not require that $s$ is the closest
center to $p$ in $s$ – we show that this inequality holds for _any_
$s^{\prime}$ and its replacement $\tilde{s}$, as long as the respective
distances to $p$ are bounded by
$\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$. Secondly, the
lemma shows the inequalities in the both directions. Both of these properties
will be useful subsequently.

######  Lemma 2.

Consider a center $s\in\mathcal{S}^{\prime}$, and let
$\tilde{s}=\rho(s)\in\tilde{\mathcal{S}}$ be its replacement found from
$\mathbb{C}_{\text{landmark}}$. Then, there exists a constant $\gamma$, such
that for any point $p\in X$, the following holds:

  * •

Either $\mathsf{d}_{G}(p,s)\geq\frac{\gamma
z\mathsf{d}_{G}(p,\mathcal{A})}{\epsilon}$, or
$\mathsf{d}_{G}(p,\tilde{s})\leq(1+\frac{\epsilon}{z})\mathsf{d}_{G}(p,s)+\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p,\mathcal{A})$,
and

  * •

Either $\mathsf{d}_{G}(p,\tilde{s})\geq\frac{\gamma
z\mathsf{d}_{G}(p,\mathcal{A})}{\epsilon}$, or
$\mathsf{d}_{G}(p,s)\leq(1+\frac{\epsilon}{z})\mathsf{d}_{G}(p,\tilde{s})+\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

###### Proof.

Let $s_{1}\in\\{s,\tilde{s}\\}$, and $s_{2}$ be the other choice. Let $R_{t}$
is the leaf node of $\mathcal{T}$ containing $s$ and $\tilde{s}$, and note
that each node along the root-leaf path $\Pi=R_{1},\ldots,R_{t}$ in
$\mathcal{T}$, contains both $s$ and $s^{\prime}$. Observe that
$s,\tilde{s}\in R^{\prime}_{t}$. Recall that $\mu$ is the parameter defined in
the construction of $\mathbb{C}_{\text{landmark}}$. We will later set the
value of $\mu$ to be $\frac{\gamma z}{\epsilon}$. We fix the point $p\in X$
for the rest of the discussion, and consider different cases.

Leaf case: $p\in R_{t}\cap X$. Since $p\in\mathcal{L}(t)=R_{t}\cap X$, the
rounding in the tuple $\tilde{d}^{1}_{t}(\cdot)$ implies that, either
$\mathsf{d}_{G}(p,s)>\frac{1}{\mu}\cdot\mathsf{d}_{G}(p,\mathcal{A})$, in
which case
$\mathsf{d}_{G}(p,\tilde{s})>\frac{1}{\mu}\cdot\mathsf{d}_{G}(p,\mathcal{A})$,
since $s$ and $\tilde{s}$ both have same rounded distance tuples. Otherwise,
$|\mathsf{d}_{G}(p,s)-\mathsf{d}_{G}(p,\tilde{s})|\leq\mu\mathsf{d}_{G}(p,\mathcal{A})$.

Internal node case: $p\not\in R_{t}$. In this case, we consider a region
$R_{i}$ along $\Pi$ such that some path $P^{i,j}\in\mathcal{P}_{i}$ separates
$p$ and $s_{1}$, and $x\in P^{i,j}$ is a separating vertex that lies between
$u$ and $v$ (as defined in Section 3.2). For the rest of the proof, we use the
shorthand $\mathsf{d}(\cdot,\cdot)\coloneqq\mathsf{d}_{G}(\cdot,\cdot)$, and
$\mathsf{d}_{i}(\cdot,\cdot)=\mathsf{d}_{G_{i}}(\cdot,\cdot)$. Let
$q^{i}_{1}=\arg\min_{q\in R_{i}}\mathsf{d}_{i}(q,s)$. We note some of the
consequences of these definitions and that of 2 in the following inequalities.

$\displaystyle\mathsf{d}_{i}(p,s_{1})$
$\displaystyle=\mathsf{d}(p,s_{1})=\mathsf{d}(p,u)+\mathsf{d}(u,v)+\mathsf{d}(v,s_{1})$
(1) $\displaystyle\mathsf{d}_{i}(u,v)$
$\displaystyle\leq\mathsf{d}_{H_{i}}(u,v)\leq\alpha\cdot\mathsf{d}_{i}(u,v)=\alpha\cdot\mathsf{d}(u,v)$
(2) $\displaystyle\mathsf{d}_{H_{i}}(u,x)+\mathsf{d}_{H_{i}}(x,v)$
$\displaystyle=\mathsf{d}_{H_{i}}(u,v)\leq\alpha\cdot\mathsf{d}_{i}(u,v)\leq\alpha\cdot\mathsf{d}(u,v)$
(3) $\displaystyle\mathsf{d}_{H_{i}}(u,v)$
$\displaystyle\leq\mu\cdot\mathsf{d}_{G}(p,s)$ (4)

In this case, we consider different cases based on the type of rounding tuple
chosen for $P^{i,j}$ while finding replacement for $s$ using rounded distance
tuples.

Case 1. Suppose there exists a $q\in R_{i}$ such that

$\mu\cdot\mathsf{d}_{i}(q^{i}_{1},s)\leq\mathsf{d}_{i}(q^{i}_{1},q)+\mathsf{d}(q,\mathcal{A})\leq\tfrac{1}{\mu}\cdot\mathsf{d}_{i}(q^{i}_{1},s)$
(5)

Note that the case assumption implies that, while defining the rounded
distance tuple $\tilde{\mathsf{D}}(s)$, we chose the first rounded tuple
$\tilde{d}^{1}_{i,j}(s,(q^{i}_{1},q^{i}_{2}))$ w.r.t. the path $P^{i,j}$, for
some $q^{i}_{2}$ satisfying (5). For the analysis of discussion of case 1 and
its subcases, we use $D\coloneqq
D(i,q^{i}_{1},q^{i}_{2})=\mathsf{d}_{i}(q^{i}_{1},q^{i}_{2})+\mathsf{d}(q^{i}_{2},\mathcal{A})$

Case 1A. $\mathsf{d}_{i}(x,q^{i}_{1})\leq\tfrac{D}{\mu^{2}}$. Since $x\in
P^{i,j}$ and $\mathsf{d}_{i}(x,q^{i}_{1})\leq\tfrac{D}{\mu^{2}}$, this implies
that $x\in Q^{i,j}(q^{i}_{1},q^{i}_{2})$. Therefore, using 1, there exists
some $l\in\mathcal{L}(i,j,q^{i}_{1},q^{i}_{2})$ such that
$\mathsf{d}_{i}(x,l)\leq\mu^{2}D$. Now consider,

$\displaystyle\mathsf{d}_{i}(s,l)$
$\displaystyle\leq\mathsf{d}_{i}(l,x)+\mathsf{d}_{i}(x,q^{i}_{1})+\mathsf{d}_{i}(q^{i}_{1},s)$
$\displaystyle\leq\mu^{2}D+\frac{D}{\mu^{2}}+\frac{D}{\mu}$
($\mathsf{d}_{i}(q^{i}_{1},s)\leq\frac{D^{2}}{\mu}$ by case assumption)
$\displaystyle\implies\ \mathsf{d}_{i}(s,l)$
$\displaystyle\leq\frac{3D^{2}}{\mu}$ (6)

Therefore,
$\tilde{d}^{1}_{i,j}(l,s)=\tilde{d}^{1}_{i,j}(l,\tilde{s})=\left\\{\left\lceil\frac{\mathsf{d}_{i}(s,l)}{\mu^{2}D}\right\rfloor\right\\}$,
which implies that
$|\mathsf{d}_{i}(s_{1},l)-\mathsf{d}_{i}(s_{2},l)|\leq\mu^{2}D$. Now, we
consider:

$\displaystyle\mathsf{d}_{i}(p,s_{2})$
$\displaystyle\leq\mathsf{d}_{i}(p,l)+\mathsf{d}_{i}(l,s_{2})$
$\displaystyle\leq\mathsf{d}_{i}(p,l)+\mathsf{d}_{i}(l,s_{1})+\mu^{2}D$ (From
above)
$\displaystyle\leq\mathsf{d}_{i}(p,x)+\mathsf{d}_{i}(x,l)+\mathsf{d}_{i}(x,l)+\mathsf{d}_{i}(x,s_{1})+\mu^{2}D$
$\displaystyle\leq\mathsf{d}_{i}(p,x)+\mathsf{d}_{i}(x,s_{1})+3\mu^{2}D$
(Since $\mathsf{d}_{i}(x,l)\leq\mu^{2}D$)
$\displaystyle\leq\mathsf{d}_{i}(p,u)+\mathsf{d}_{i}(u,x)+\mathsf{d}_{i}(x,v)+\mathsf{d}_{i}(v,s_{1})+3\mu^{2}D$
$\displaystyle\leq\mathsf{d}(p,u)+\mathsf{d}(v,s_{1})+\mathsf{d}_{H_{i}}(u,x)+\mathsf{d}_{H_{i}}(x,v)+3\mu^{2}D$
(Using (1))
$\displaystyle\leq\mathsf{d}(p,s_{1})+\mu\cdot\mathsf{d}(p,s_{1})+3\mu^{2}D$
(Using (4))
$\displaystyle\leq(1+\mu)\cdot\mathsf{d}(p,s_{1})+3\mu\mathsf{d}_{i}(p,s)$
(Using case assumption: (5))

Substituting $s_{1}=s$ and $s_{2}=\tilde{s}$, we obtain:

$\displaystyle\mathsf{d}(p,\tilde{s})\leq\mathsf{d}_{i}(p,\tilde{s})$
$\displaystyle\leq(1+\mu)\cdot\mathsf{d}(p,s)+3\mu\cdot\mathsf{d}_{i}(p,s)$
(First inequality follows since $G_{i}$ is a subgraph of $G$)
$\displaystyle\leq(1+4\mu)\cdot\mathsf{d}(p,s)$ (7)

and substituting $s_{1}=s$ and $s_{1}=\tilde{s}$, we obtain

$\displaystyle\mathsf{d}_{i}(p,s)$
$\displaystyle\leq(1+\epsilon)\mathsf{d}(p,\tilde{s})+3\mu\mathsf{d}_{i}(p,s)$
$\displaystyle(1-3\mu)\cdot\mathsf{d}(p,s)\leq(1-3\mu)\cdot\mathsf{d}_{i}(p,s)$
$\displaystyle\leq(1+\mu)\mathsf{d}(p,\tilde{s})$ (First inequality follows
since $G_{i}$ is a subgraph of $G$) $\displaystyle\implies\ \mathsf{d}(p,s)$
$\displaystyle\leq\frac{1+\mu}{1-3\mu}\cdot\mathsf{d}(p,\tilde{s})\leq(1+13\mu)\cdot\mathsf{d}(p,\tilde{s})$
(8)

Case 1B. $\mathsf{d}_{i}(x,q^{i}_{1})>\frac{D}{\mu^{2}}$. First, (5) implies
that $\mathsf{d}_{i}(q^{i}_{1},s)\leq\frac{1}{\mu}D$. Therefore, by the
definition of rounded distance tuple
$\tilde{d}^{1}_{i,j}(s,(q^{i}_{1},q^{i}_{2}))$, we have the following
inequality

$\mathsf{d}_{i}(s,q^{i}_{1})-\mathsf{d}_{i}(\tilde{s},q^{i}_{1})|\leq\mu D$
(9)

Therefore, consider:

$\displaystyle\mathsf{d}_{i}(s,\tilde{s})\leq\mathsf{d}_{i}(s,q^{i}_{1})+\mathsf{d}_{i}(q^{i}_{1},\tilde{s})$
$\displaystyle\leq 2\mathsf{d}_{i}(q^{i}_{1},s)+\mu D$
$\displaystyle\leq\frac{2}{\mu}D+\mu D\leq\frac{3}{\mu}D$ $\displaystyle\leq
3\mu\cdot\mathsf{d}_{i}(x,q^{i}_{1})$ (From assumption of Case 1B)
$\displaystyle\leq
3\mu\cdot(\mathsf{d}_{i}(x,s_{1})+\mathsf{d}_{i}(s_{1},s_{2})+d_{i}(s_{2},q^{i}_{1}))$

By rearranging the last inequality, we obtain that:

$\displaystyle\mathsf{d}_{i}(s,\tilde{s})$
$\displaystyle\leq\frac{3\mu}{(1-3\mu)}\cdot(\mathsf{d}_{i}(x,s_{1})+\mathsf{d}_{i}(s_{2},q^{i}_{1}))$
$\displaystyle\leq
9\mu\cdot(\mathsf{d}_{i}(x,s_{1})+\mathsf{d}_{i}(s,q^{i}_{1})+\mu D)$ (Using
(9)) $\displaystyle\leq
9\mu\cdot(\mathsf{d}_{i}(x,v)+\mathsf{d}_{i}(v,s_{1})+\mathsf{d}_{i}(p,s)+\mathsf{d}_{i}(p,s))$
($\mu D\leq\mathsf{d}_{i}(q^{i}_{1},s)$ by (5) and
$\mathsf{d}_{i}(q^{i}_{1},s)\leq\mathsf{d}_{i}(p,s)$ by the choice of
$q^{i}_{1}$) $\displaystyle\leq
9\mu\cdot\left(\mathsf{d}_{H_{i}}(x,v)+\mathsf{d}_{i}(v,s_{1})+2\mathsf{d}_{i}(p,s)\right)$
$\displaystyle\leq
9\mu\cdot\left(\mathsf{d}_{H_{i}}(u,v)+\mathsf{d}_{i}(p,s_{1})+2\mathsf{d}_{i}(p,s)\right)$

Where the last inequality follows from the fact that, $u,\ldots,x,\ldots,v$ is
a shortest path in $H_{i}$, and $p,\ldots,v,\ldots,s_{1}$ is a shortest path
in $G$ as well as $G_{i}$. Therefore,

$\displaystyle\mathsf{d}_{i}(s,\tilde{s})$ $\displaystyle\leq
9\mu\cdot\left(\mu\cdot\mathsf{d}(p,s_{1})+3\mathsf{d}_{i}(p,s)\right)\leq
27\mu\cdot(\mathsf{d}(p,s_{1})+\mathsf{d}_{i}(p,s))$

Therefore,

$\displaystyle\mathsf{d}_{i}(p,s_{2})$
$\displaystyle\leq\mathsf{d}_{i}(p,s_{1})+27\mu\cdot(\mathsf{d}(p,s_{1})+\mathsf{d}_{i}(p,s))$
(10)

By substituting $s_{1}=s$, and $s_{2}=\tilde{s}$ in (10), we obtain:

$\displaystyle\mathsf{d}(p,\tilde{s})$
$\displaystyle\leq\mathsf{d}_{i}(p,s)+27\mu(\mathsf{d}_{G}(p,s_{1})+\mathsf{d}_{i}(p,s))$
$\displaystyle=\mathsf{d}(p,s)+54\mu\cdot\mathsf{d}(p,s)=(1+54\mu)\mathsf{d}(p,s)$
(11)

Where we use that
$\mathsf{d}_{i}(p,s_{1})=\mathsf{d}(p,s_{1})=\mathsf{d}(p,s)$. Then, by
substituting $s_{1}=\tilde{s}$ and $s_{2}=s$ in (10), we obtain:

$\displaystyle\mathsf{d}_{i}(p,s)$
$\displaystyle\leq\mathsf{d}_{i}(p,\tilde{s})+27\mu\cdot(\mathsf{d}(p,\tilde{s})+\mathsf{d}_{i}(p,s))$
$\displaystyle\implies(1-27\mu)\mathsf{d}(p,s)\leq(1-27\mu)\mathsf{d}_{i}(p,s)$
$\displaystyle\leq\mathsf{d}(p,\tilde{s})+27\mu\cdot\mathsf{d}(p,\tilde{s})$
(Since $\mathsf{d}_{i}(p,s_{1})=\mathsf{d}(p,s_{1})=\mathsf{d}(p,\tilde{s})$)
$\displaystyle\implies\mathsf{d}(p,s)$
$\displaystyle\leq\frac{1+27\mu}{1-27\mu}\cdot\mathsf{d}(p,\tilde{s})\leq(1+1539\mu)\mathsf{d}(p,\tilde{s})$
(12)

Case 2. Suppose there exists no point $q\in R_{i}$ satisfying (5). Then, for
any point $q$ (and in particular, for $q=p$), exactly one of the following
inequalities holds:

$\displaystyle\mathsf{d}(q,\mathcal{A})+\mathsf{d}_{i}(q,q^{i}_{1})>\frac{1}{\mu}\mathsf{d}_{i}(q^{i}_{1},s)$
(13) $\displaystyle\textbf{ OR
}\mathsf{d}(q,\mathcal{A})+\mathsf{d}_{i}(q,q^{i}_{1})<\mu\mathsf{d}_{i}(q^{i}_{1},s)$
(14)

In this case, while finding replacement for $s$, we choose the second rounded
distance tuple $\tilde{d}^{2}_{i,j}(s,(q^{i}_{1},q^{i}_{3},q^{i}_{4}))$ in the
rounded tuple $\tilde{\mathsf{D}}(s)$, with the following properties. If there
exists a point $q\in R_{i}$ satisfying (13), then $q^{i}_{3}$ is chosen to be
the one with smallest value on the left hand side; otherwise $q^{i}_{3}=\bot$.
Analogously, if there exists a point $q\in R_{i}$ satisfying (14), then
$q^{i}_{4}$ is chosen to be the one with largest value on the left hand side;
otherwise $q^{i}_{4}=\bot$. Note that at least one of the two points
$q^{i}_{3}$ and $q^{i}_{4}$ is not equal to $\bot$ due to case assumption.
Thus, the following inequality (inequalities) holds:

$\displaystyle\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{4})+\mathsf{d}(q^{i}_{4},\mathcal{A})\right)\leq\mathsf{d}_{i}(q^{i}_{1},s)\leq\mu\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{3})+\mathsf{d}(q^{i}_{3},\mathcal{A})\right)$
(15)

where, we drop an inequality from the requirement if the corresponding point
$q^{i}_{3}$ or $q^{i}_{4}$ is $\bot$. Thus,
$\tilde{\mathsf{d}}^{2}_{i,j}(s,(q^{i}_{1},q^{i}_{3},q^{i}_{4}))=\texttt{true}$.
Therefore,
$\tilde{\mathsf{d}}^{2}_{i,j}(\tilde{s},(q^{i}_{1},q^{i}_{3},q^{i}_{4}))=\texttt{true}$,
which implies that:

$\displaystyle\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{4})+\mathsf{d}(q^{i}_{4},\mathcal{A})\right)\leq\mathsf{d}_{i}(q^{i}_{1},\tilde{s})\leq\mu\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{3})+\mathsf{d}(q^{i}_{3},\mathcal{A})\right)$
(16)

Again, with the same caveat about dropping the appropriate inequality.

Now we consider two cases depending on which inequality from (13) and (14) is
satisfied by $p$.

Case 2A. Suppose
$\mathsf{d}(p,\mathcal{A})+\mathsf{d}_{i}(p,q^{i}_{1})>\frac{1}{\mu}\mathsf{d}_{i}(q^{i}_{1},s)$.
Then, by the choice of $q^{i}_{3}$, we have that:

$\displaystyle\mathsf{d}_{i}(s,\tilde{s})$
$\displaystyle\leq\mathsf{d}_{i}(s,q^{i}_{1})+\mathsf{d}_{i}(\tilde{s},q^{i}_{1})$
$\displaystyle\leq
2\mu\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{3})+\mathsf{d}(q^{i}_{3},\mathcal{A})\right)$
(From (15) and (16)) $\displaystyle\leq
2\mu\cdot\left(\mathsf{d}_{i}(q^{i}_{1},p)+\mathsf{d}(p,\mathcal{A})\right)$
(Since $q^{i}_{3}$ is a point minimizing the LHS of (13)) $\displaystyle\leq
2\mu\cdot\left(\mathsf{d}_{i}(p,s)+\mathsf{d}_{i}(q_{i},s)+\mathsf{d}(p,\mathcal{A})\right)$
$\displaystyle\leq
2\mu\cdot\left(2\mathsf{d}_{i}(p,s)+\mathsf{d}(p,\mathcal{A})\right)$ (Since
$q^{i}_{1}$ is a point minimizing $\mathsf{d}_{i}(\cdot,s)$)
$\displaystyle\leq 4\mu(\mathsf{d}_{i}(p,s)+\mathsf{d}(p,\mathcal{A}))$

Therefore, we obtain the following inequality.

$\displaystyle\mathsf{d}(p,s_{1})\leq\mathsf{d}(p,s_{2})+\mathsf{d}(s_{1},s_{2})$
$\displaystyle\leq\mathsf{d}(p,s_{2})+\mathsf{d}_{i}(s_{1},s_{2})$
$\displaystyle\mathsf{d}(p,s_{2})+4\mu\cdot(\mathsf{d}_{i}(p,s)+\mathsf{d}(p,\mathcal{A}))$
(17)

By plugging in $s_{1}=s$ and $s_{2}=\tilde{s}$, we obtain:

$\displaystyle\mathsf{d}(p,s)$
$\displaystyle\leq\mathsf{d}(p,\tilde{s})+4\mu\cdot\mathsf{d}(p,s)+4\mu\cdot\mathsf{d}(p,\mathcal{A})$
$\displaystyle\implies\ (1-4\mu)\cdot\mathsf{d}(p,s)$
$\displaystyle\leq\mathsf{d}(p,\tilde{s})+4\mu\cdot\mathsf{d}(p,\mathcal{A})$
$\displaystyle\implies\ \mathsf{d}(p,s)$
$\displaystyle\leq(1+8\mu)\cdot\mathsf{d}(p,\tilde{s})+12\mu\cdot\mathsf{d}(p,\mathcal{A})$
(18)

And by plugging in $s_{1}=\tilde{s}$ and $s_{2}=s$, we obtain:

$\displaystyle\mathsf{d}(p,\tilde{s})$
$\displaystyle\leq(1+4\mu)\cdot\mathsf{d}(p,s)+4\mu\cdot\mathsf{d}(p,\mathcal{A})$
(19)

Case 2B. Suppose
$\mathsf{d}(p,\mathcal{A})+\mathsf{d}_{i}(p,q^{i}_{1})<\mu\mathsf{d}_{i}(q^{i}_{1},s)$.
Then, by the choice of $q^{i}_{4}$, it holds that
$\mathsf{d}_{i}(q^{i}_{1},s_{1})>\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{4})+\mathsf{d}(q^{i}_{4},\mathcal{A})\right)$,
since both $s$ and $\tilde{s}$ satisfy this inequality. Therefore,

$\displaystyle\mathsf{d}(p,s_{1})=\mathsf{d}_{i}(p,s_{1})$
$\displaystyle\geq\mathsf{d}_{i}(q^{i}_{1},s_{1})-\mathsf{d}_{i}(p,q^{i}_{1})$
$\displaystyle\geq\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q^{i}_{1},q^{i}_{4})+\mathsf{d}(q^{i}_{4},\mathcal{A})\right)-\mathsf{d}_{i}(p,q^{i}_{1})$
(From above)
$\displaystyle\geq\frac{1}{\mu}\cdot\left(\mathsf{d}_{i}(q^{i}_{1},p)+\mathsf{d}(p,\mathcal{A})\right)-\mathsf{d}_{i}(p,q^{i}_{1})$
(By the choice of $q^{i}_{4}$)
$\displaystyle\geq\frac{1}{\mu}\cdot\mathsf{d}(p,\mathcal{A})$

Thus, the above inequality shows that in case 2B, both $\mathsf{d}(p,s)$ and
$\mathsf{d}(p,\tilde{s})$ are larger than
$\frac{1}{\mu}\mathsf{d}(p,\mathcal{A})$.

Thus, by combining all the cases, we obtain that, either
$\mathsf{d}(p,s_{1})>\frac{1}{\mu}\mathsf{d}(p,\mathcal{A})$, or
$\mathsf{d}(p,s_{2})\leq(1+c\mu)\cdot\mathsf{d}(p,s_{1})+c^{\prime}\mu\mathsf{d}(p,s_{2})$,
for some constants $1\leq c,c^{\prime}\leq 1539$. Let
$\gamma=\max\left\\{c,c^{\prime}\right\\}=1539$. Therefore, by setting
$\mu=\gamma\cdot\frac{\epsilon}{z}$, we obtain that: either
$\mathsf{d}(p,s_{1})>\frac{\gamma z\mathsf{d}(p,\mathcal{A})}{\epsilon}$, or
$\mathsf{d}(p,s_{2})\leq(1+\frac{\epsilon}{z})\mathsf{d}(p,s_{1})+\frac{\epsilon}{z}\mathsf{d}(p,\mathcal{A})$.
∎

#### Reverse direction.

Now, we aim to prove the ``reverse direction''. Specifically, we focus on a
point $p\in X$ with $\tilde{s}_{1}\in\tilde{\mathcal{S}}$ being its closest
center in $\tilde{\mathcal{S}}$. Then we show that if
$\mathsf{d}_{G}(p,\tilde{s}_{1})\leq\frac{10z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$,
then
$\mathsf{d}_{G}(p,\mathcal{S})\leq(1+\mathcal{O}(\epsilon/z))\cdot\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
As before, this proof is organized in the following claims, based on different
cases. Before this, we need the following lemma whose proof follows trivially
from Lemma 18 of [18].

######  Lemma 3.

Consider any $s\in\mathcal{S}_{\text{net}}$ such that $X^{\prime}_{s}=\\{q\in
X_{s}:\mathsf{d}_{G}(q,\mathcal{A})<1\\}$. Let
$q^{\prime}=\operatorname*{arg\,min}_{\\{q\in
X^{\prime}_{s}\\}}\mathsf{d}_{G}(q,\mathcal{A})+\mathsf{d}_{G}(q,s)$. Then,
without loss of generality, we can assume that for all points $p$ with
$\mathsf{d}_{G}(p,\mathcal{A})<1$,
$(\mathsf{d}_{G}(p,\mathcal{A})+\mathsf{d}_{G}(p,s))>\frac{\epsilon^{2}}{8z^{2}}\cdot(\mathsf{d}_{G}(q^{\prime},\mathcal{A})+\mathsf{d}_{G}(q^{\prime},s))$.

Thus, we assume the property guaranteed by Lemma 3, and proceed to proving the
following claims.

######  Claim 6.

Consider a point $p\in X$ with (1) $\mathsf{d}_{G}(p,\mathcal{A})<1$, and (2)
$\tilde{s}_{1}$ is the closest center in $\tilde{\mathcal{S}}$ to $p$, with
$\mathsf{d}_{G}(p,\tilde{s}_{1})\leq\frac{10z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
Then,
$\mathsf{d}_{G}(p,\mathcal{S})\leq(1+\mathcal{O}(\epsilon/z))\cdot\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

###### Proof.

Let $s$ be the closest center in $\mathcal{S}$ to and from $p$. Note that
since $\mathsf{d}_{G}(p,\mathcal{A})<1$, $s\in\mathcal{S}_{\text{net}}$, and
$\rho(s)=\tilde{s}\in\mathbb{C}_{\text{net}}$. Furthermore, by the condition
of lemma, $\mathsf{d}_{G}(p,\tilde{s}_{1})\leq\mathsf{d}_{G}(p,\tilde{s})$. We
consider three cases.

First, suppose there exists some $s_{1}\in\mathcal{S}_{\text{net}}$ such that
$\rho(s_{1})=\tilde{s}_{1}$. 333Note here that it may be the case that there
also exists some $s^{\prime}\in\mathcal{S}_{\text{net-sub}}$ for which
$\rho(s^{\prime})=\tilde{s}_{1}$. But, in this analysis, the existence of
$s_{1}\in\mathcal{S}_{\text{net}}$ is sufficient. Then, the set
$X^{\prime}_{s_{1}}=\\{q\in X_{s_{1}}:\mathsf{d}_{G}(q,\mathcal{A})<1\\}$ is
non-empty. Let $q^{\prime}=\operatorname*{arg\,min}_{q\in
X^{\prime}_{s_{1}}}\mathsf{d}_{G}(q,\mathcal{A})+\mathsf{d}_{G}(q,s_{1})$. It
follows that
$\mathsf{d}_{G}(s_{1},\tilde{s}_{1})\leq\frac{\epsilon^{3}}{z^{3}}\cdot\mathsf{d}_{G}(q^{\prime},\mathcal{A})$.
Then, by Lemma 3,

$\displaystyle\mathsf{d}_{G}(p,s_{1})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathsf{d}_{G}(s_{1},\tilde{s}_{1})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\frac{\epsilon^{3}}{z^{3}}\cdot\mathsf{d}_{G}(q^{\prime},\mathcal{A})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\frac{\epsilon^{3}}{z^{3}}\cdot(\mathsf{d}_{G}(q^{\prime},\mathcal{A})+\mathsf{d}_{G}(q^{\prime},s_{1}))$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\frac{\epsilon^{3}}{z^{3}}\cdot\frac{8z^{2}}{\epsilon^{2}}\cdot(\mathsf{d}_{G}(p,\mathcal{A})+\mathsf{d}_{G}(p,s_{1}))$
$\displaystyle=\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon/z)\cdot(\mathsf{d}_{G}(p,\mathcal{A})+\mathsf{d}_{G}(p,s_{1}))$

Hence,

$\mathsf{d}_{G}(p,s)\leq\mathsf{d}_{G}(p,s_{1})\leq(1+\mathcal{O}(\epsilon/z))\cdot\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A}).$

In the second case, there exists some $s_{1}\in\mathcal{S}_{\text{support}}$
such that $\rho(s_{1})=f(s_{1})=\tilde{s}_{1}$.

$\mathsf{d}_{G}(p,\tilde{s}_{1})\geq\mathsf{d}_{G}(p,s_{1})-\mathcal{O}(\epsilon^{2}/z^{2})\geq\mathsf{d}_{G}(p,s)-\mathcal{O}(\epsilon^{2}/z^{2})$

Now, as $s_{1}$ was replaced by $\tilde{s}_{1}\in\mathcal{S}_{\text{support}}$
although $\mathsf{d}_{G}(p,\tilde{s})>\mathsf{d}_{G}(p,\tilde{s}_{1})$, it
must be that $\mathsf{d}_{G}(p,s)>\epsilon/z$, by our replacement scheme. Thus

$\displaystyle\mathsf{d}_{G}(p,s)\leq\mathsf{d}_{G}(p,s_{1})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathsf{d}_{G}(s_{1},\tilde{s}_{1})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon^{2}/z^{2})$
$\displaystyle\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathcal{O}(\epsilon/z)\cdot\mathsf{d}_{G}(p,s)$

Therefore,
$\mathsf{d}_{G}(p,s)\leq(1+\mathcal{O}(\epsilon/z))\cdot\mathsf{d}_{G}(p,\tilde{s}_{1})\leq(1+\mathcal{O}(\epsilon/z))\cdot\mathsf{d}_{G}(p,\tilde{s}_{1})+(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
∎

######  Claim 7.

Consider a point $p\in X$ with $\mathsf{d}_{G}(p,\mathcal{A})\geq 1$, and
$\tilde{s}_{1}$ is the closest center to $p$ from $\tilde{\mathcal{S}}$ such
that $\rho(s_{1})=\tilde{s}_{1}$, where
$s_{1}\in\mathcal{S}_{\text{net}}\cup\mathcal{S}_{\text{support}}$. Then,
$\mathsf{d}_{G}(p,\mathcal{S})\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.

###### Proof.

We consider two cases. If $s_{1}\in\mathcal{S}_{\text{net}}$, then
$\mathsf{d}_{G}(s_{1},\tilde{s}_{1})\leq\frac{\epsilon^{3}}{z^{3}}\leq\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
Alternatively, if $s_{1}\in\mathcal{S}_{\text{support}}$, then
$\mathsf{d}_{G}(s_{1},\tilde{s}_{1})\leq\frac{\epsilon^{2}}{z^{2}}\leq\frac{\epsilon^{2}}{z^{2}}\cdot\mathsf{d}_{G}(p,\mathcal{A})$.
Here, we use the fact that $\mathsf{d}_{G}(p,\mathcal{A})\geq 1$ in each of
the inequalities. Then, the claim follows since:

$\mathsf{d}_{G}(p,\mathcal{S})\leq\mathsf{d}_{G}(p,s_{1})\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\mathsf{d}_{G}(s_{1},\tilde{s}_{1})\leq\mathsf{d}_{G}(p,\tilde{s}_{1})+\frac{\epsilon}{z}\cdot\mathsf{d}_{G}(p,\mathcal{A}).$

∎

##### Putting Everything Together.

First, we prove the error bound in the following lemma.

######  Lemma 4.

For any $\mathcal{S}\in\mathbb{C}^{k}$, there exists a
$\tilde{\mathcal{S}}\in\mathbb{C}^{k}$ with the following property. For any
point $p\in X$, if
$\mathsf{cost}(p,\mathcal{S})\leq\left(\frac{10z}{\epsilon}\right)^{z}\mathsf{d}(p,\mathcal{A})$,
or
$\mathsf{cost}(p,\tilde{\mathcal{S}})\leq\left(\frac{10z}{\epsilon}\right)^{z}\mathsf{d}(p,\mathcal{A})$,
then

$|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|\leq\frac{\epsilon}{z\log(z/\epsilon)}\cdot\left(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A})\right).$

###### Proof.

Let $\mu\geq 0$ be a large enough constant. By combining 3, 4, 5, and Lemma 2,
and by appropriately rescaling $\epsilon$, we conclude that for every point
$p\in X$ with $\mathsf{d}_{G}(p,\mathcal{S})\leq\frac{9\mu
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$, the following holds.

$\displaystyle\mathsf{d}_{G}(p,\tilde{\mathcal{S}})$
$\displaystyle\leq\left(1+\epsilon/z\right)\cdot\mathsf{d}_{G}(p,\mathcal{S})+(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$
(20) $\displaystyle\implies\ \mathsf{cost}(p,\tilde{\mathcal{S}})$
$\displaystyle\leq(1+\epsilon)\cdot\mathsf{cost}(p,\mathcal{S})+\epsilon\cdot\mathsf{cost}(p,\mathcal{A})$
(21)

Here, we use Lemma 1 in the last step.

Similarly, by combining 6, 7, and Lemma 2, and appropriately rescaling
$\epsilon$, we conclude that for every point $p\in X$ with
$\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\frac{9\mu
z}{\epsilon}\mathsf{d}_{G}(p,\mathcal{A})$, the following holds.

$\displaystyle\mathsf{d}_{G}(p,\mathcal{S})$
$\displaystyle\leq\left(1+\epsilon/z\right)\cdot\mathsf{d}_{G}(p,\tilde{\mathcal{S}})+(\epsilon/z)\cdot\mathsf{d}_{G}(p,\mathcal{A})$
(22) $\displaystyle\implies\ \mathsf{cost}(p,\tilde{\mathcal{S}})$
$\displaystyle\leq(1+\epsilon)\cdot\mathsf{cost}(p,\mathcal{S})+\epsilon\cdot\mathsf{cost}(p,\mathcal{A})$
(23)

Where we again use Lemma 1 in the last step.

Now, using (20), we can infer that for any $\lambda\leq 9\mu$,

$\mathsf{d}_{G}(p,\mathcal{S})\leq\frac{\lambda
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})\ \ \implies\ \
\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\frac{3\lambda
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$ (24)

Similarly, using (22), we can infer that for any $\lambda\leq 9\mu$,

$\mathsf{d}_{G}(p,\tilde{\mathcal{S}})\leq\frac{\lambda
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})\ \ \implies\ \
\mathsf{d}_{G}(p,\mathcal{S})\leq\frac{3\lambda
z}{\epsilon}\mathsf{d}_{G}(p,\mathcal{A})$ (25)

Therefore, by applying (24) and (25) with $\lambda\leftarrow\mu$, we can
conclude that either both $\mathsf{d}_{G}(p,\mathcal{S})$ and
$\mathsf{d}_{G}(p,\mathcal{S})$ are larger than $\frac{3\mu
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$, and we are done. Otherwise,
both are smaller than $\frac{9\mu
z}{\epsilon}\cdot\mathsf{d}_{G}(p,\mathcal{A})$. Then, by using (21) and (23),
we obtain that for any such point $p\in X$,

$\displaystyle|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|$
$\displaystyle\leq
2\epsilon\cdot\left(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\tilde{\mathcal{S}})+\mathsf{cost}(p,\mathcal{A})\right)$
$\displaystyle\implies(1-2\epsilon)\cdot|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|$
$\displaystyle\leq
4\epsilon\cdot\left(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A})\right)$
(Using
$\mathsf{cost}(p,\tilde{\mathcal{S}})\leq\mathsf{cost}(p,\mathcal{S})+|\mathsf{cost}(p,\tilde{\mathcal{S}})-\mathsf{cost}(p,\mathcal{S})|$)
$\displaystyle\implies\
|\mathsf{cost}(p,\mathcal{S})-\mathsf{cost}(p,\tilde{\mathcal{S}})|$
$\displaystyle\leq
12\epsilon\left(\mathsf{cost}(p,\mathcal{S})+\mathsf{cost}(p,\mathcal{A})\right)$
(26)

Thus, we obtain the lemma by a final rescaling
$\epsilon\leftarrow\frac{\epsilon}{cz\log(z/\epsilon)}$ for some large enough
constant $c$. ∎

Now, we bound the size of the centroid set.

######  Lemma 5.

$|\mathbb{C}|=\exp\left(\mathcal{O}\left(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|\right)\right)$.

###### Proof.

Recall that
$\mathbb{C}\coloneqq\mathbb{C}_{\text{landmark}}\cup\mathbb{C}_{\text{support}}\cup\mathbb{C}_{\text{net}}$.
First, the size of $\mathbb{C}_{\text{support}}$ is bounded by
$(\Delta(z^{2}/\epsilon^{2}))^{\ell}|X|$, due to Proposition 4. Since
$\ell=\Theta(z/\epsilon)$, this is equal to
$(z/\epsilon)^{\mathcal{O}(z/\epsilon)}\cdot|X|$. Next, we bound
$\mathbb{C}_{\text{net}}$. The size of each $B^{\prime}_{i}$, which is an
$(\epsilon^{3}/z^{3})\mathsf{d}_{G}(p_{i},\mathcal{A})$-net of $B_{i}$, can be
upper bounded by $\mathcal{O}(z^{8}\epsilon^{-8})$ by using Proposition 3.
Hence, the size of $\mathbb{C}_{\text{net}}$ is
$\mathcal{O}(|X|z^{8}\epsilon^{-8})$.

Now, we bound $\mathbb{C}_{\text{landmark}}$. Note that
$\mathbb{C}_{\text{landmark}}$ contains at most one point per rounded distance
tuple and each leaf. Note that there are at most $\mathcal{O}(|X|)$ leaves,
and thus the same number of root-leaf paths. Now, fix a root-leaf path
$\Pi=(R_{1},R_{2},\ldots,R_{t})$, and the corresponding collection of
shortest-path separators $\mathcal{P}$ of size $\mathcal{O}(\log|X|)$. For
each $P^{i,j}\in\mathcal{P}$, we may select either the first or the second
rounded distance tuple. If, for a path $P^{i,j}$, we select first rounded
distance tuple, then, first we need to select points $q_{1}$ and $q_{2}$,
which leads to $|X|^{2}$ choices. Then, there are at most
$\mathcal{O}((z/\mu)^{4})$ landmark points along the path, and each distance
can take at most $\mathcal{O}(z^{4}/\epsilon^{4})$ values. On the other hand,
if we select the second rounded distance tuple, we need to select $q_{1}$,
$q_{3}$ and $q_{4}$, which leads to $|X|^{3}$ choices. Thus, for a particular
$P^{i,j}$, the number of choices is upper bounded by
$|X|^{\mathcal{O}(1)}\cdot(z/\epsilon)^{\mathcal{O}(z^{4}/\epsilon^{4})}$.
Thus, the total number of rounded distance tuples is upper bounded
$|X|^{\mathcal{O}(\log|X|)}\cdot(z/\epsilon)^{\mathcal{O}(z^{4}\log|X|/\epsilon^{4})}$.
This is also the upper bound on the size of $\mathbb{C}_{\text{landmark}}$.

Therefore, the size of $\mathbb{C}$ is upper bounded by
$\exp\left(\mathcal{O}(\log^{2}|X|+z^{8}\epsilon^{-8}\log|X|\log(z/\epsilon))\right)$.
Finally, we account for rescaling of $\epsilon$ by
$\epsilon/(cz\log(z/\epsilon))$, which implies that the actual bound on
$|\mathbb{C}|$ is:

$\exp\left(\mathcal{O}\left(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|\right)\right).$

∎

##  4 Applications to Geometric Intersection Graphs

In this section, we apply Theorem 3 on various geometric intersection graphs
in order to obtain coresets of size that is independent of $n$. First, we
consider the case of Euclidean weighted UDG metrics and
$\ell_{\infty}$-weighted USGs, and explain why they satisfy the two canonical
properties. Subsquently, we consider UDG and USG with general $\ell_{p}$ norm
weights (Section 4.3). Finally, we consider the special case of unweighted
UDGs with bounded degree (Section 4.4), where we only discuss the
modifications in the arguments required to see that the corresponding metrics
also satisfy these properties.

###  4.1 Euclidean Weighted Unit Disk Graphs.

It is straightforward to verify that Euclidean weighted UDGs satisfy Locally
Euclidean property. Indeed, consider an embedding $\lambda:V(G)\to^{2}$
realizing a UDG $G$. There is an edge between two vertices if and only if the
euclidean distance between the corresponding two points is at most $2$.
Furthermore, the weight of such an edge is exactly the euclidean distance
between the two points. It follows that $c_{1}=c_{2}=2$ and $c_{3}=c_{4}=1$
satisfies the property.

As for the Planar Spanner property, we use the following known result.

######  Proposition 6.

[Li, Calinescu, and Wan [37]] For any UDG $G$, there is a planar spanner $H$
such that for any $u,v\in V(H)$,
$\mathsf{d}_{G}(u,v)\leq\mathsf{d}_{H}(u,v)\leq 2.42\cdot\mathsf{d}_{G}(u,v)$.

Thus, Theorem 3 yields the following theorem for Euclidean-weighted UDGs.

######  Theorem 4.

Consider the metric space $(V,\mathsf{d}_{G})$ induced by any Euclidean
weighted unit-disk graph $G=(V,E)$, a set $P\subseteq V$ with $n$ distinct
points, and two positive integers $k$ and $z$. Then there exists a polynomial
time algorithm that constructs with probability at least $1-\delta$ a coreset
for $(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k\log^{3}(1/\delta))$, where $z$ is a
constant, $\beta=\mathcal{O}(z\log z)$, and $\delta<1/4$.

###  4.2 $\ell_{\infty}$-Weighted Unit Square Graphs

Preliminaries. Consider a point $q$ in the plane with coordinates $(a,b)$. For
a $p\geq 1$, let $||(a,b)||_{p}\coloneqq\left(|a|^{p}+|b|^{p}\right)^{1/p}$
for $p\leq\infty$, and
$||(a,b)||_{\infty}\coloneqq\lim_{p\to\infty}||(a,b)||_{p}=\max\left\\{|a|,|b|\right\\}$.
We have the following relation between different norms.

######  Observation 3.

For any $(a,b)\in^{2}$ and for any $1\leq p\leq q\leq\infty$, it holds that
$||(a,b)||_{p}\leq||(a,b)||_{q}\leq\sqrt{2}\cdot||(a,b)||_{p}$.

A _unit square_ centered at $p$, denoted by $S(p)$, is the axis-parallel
square of sidelength $2$ with $p$ at its center, along with its
interior.444Henceforth, whenever we refer to a square, we always refer to the
points on the boundary as well as its interior. Alternatively, $S(p)$ is the
set of points $q$ such that $||p-q||_{\infty}\leq 1$, where
$||\cdot||_{\infty}$ denotes the $\ell_{\infty}$ norm, defined as
$||(a,b)||_{\infty}=\max\\{|a|,|b|\\}$.

A Unit Square Graph (USG) with a set of points $P\subset^{2}$ is the
intersection graph of unit squares centered at each point in $P$. Observe that
$p,q\in P$, $\\{p,q\\}$ is an edge in the USG if and only if the unit squares
$S(p)$ and $S(q)$ intersect. The weight of an edge $\\{p,q\\}$ is defined to
be $||p-q||_{\infty}$. Observe that the weights of the edges are between $0$
and $2$.

##### Canonical Geometric Properties.

First, we argue that $\ell_{\infty}$-weighted USGs satisfy the Locally
Euclidean property. Consider a USG $G$ with an embedding
$\lambda:V(G)\to^{2}$. Via 3, it follows that if for some $u,v\in V(G)$, if
$||\lambda(u)-\lambda(v)||_{2}=|\lambda(u)\lambda(v)|>2$, then
$||\lambda(u)-\lambda(v)||_{\infty}>2$, which implies that $uv\not\in E(G)$.
On the other hand, if
$||\lambda(u)-\lambda(v)||_{2}=|\lambda(u)\lambda(v)|\leq\sqrt{2}$, then
$||\lambda(u)-\lambda(v)||_{\infty}\leq 2$, which implies that $uv\in E(G)$.
Furthermore, the weight of such an edge is
$w(uv)=||\lambda(u)-\lambda(v)||_{\infty}$, which implies that
$|\lambda(u)\lambda(v)|\leq w(u,v)\leq\sqrt{2}\cdot|\lambda(u)\lambda(v)|$.
Thus, $\ell_{\infty}$-weighted USGs satisfy Locally Euclidean property with
$c_{1}=\sqrt{2},c_{2}=2,c_{3}=1,c_{4}=\sqrt{2}$.

Recall that a constant planar spanner for euclidean edge-weighted UDGs was
shown in [37]. However, a similar spanner for $L_{\infty}$ edge-weighted USGs
was not known before. We bridge this gap by showing the existence of exactly
such a spanner in the following theorem. Theorem 5 is interesting on its own
and we expect that, similar to planar spanners for UDGs, planar spanners for
USGs would find applications beyond clustering. To keep the flow of the paper,
we defer the proof of Theorem 5 to the following section, Section 5.

######  Theorem 5.

Let $P$ be a set of points satisfying the general position assumptions, and
let $G=(P,E)$ be the unit square graph associated with $P$, such that the
weight of an edge $uv$ is equal to $||u-v||_{\infty}$. Then, there exists a
planar subgraph $H$ of $G$ such that for any two points $a,b\in P$,
$\mathsf{d}_{G}(a,b)\leq\mathsf{d}_{H}(a,b)\leq 3\mathsf{d}_{G}(a,b)$.

Thus, USGs satisfy the planar spanner property with stretch factor $\alpha=3$.
Then, by applying Theorem 1, we obtain the following theorem.

######  Theorem 6.

Consider the metric space $(V,\mathsf{d}_{G})$ induced by any $L_{\infty}$
weighted unit square graph $G=(V,E)$, a set $P\subseteq V$ with $n$ distinct
points, and two positive integers $k$ and $z$. Then there exists a polynomial-
time algorithm that constructs with probability at least $1-\delta$ a coreset
for $(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k\log^{3}(1/\delta))$, where $z$ is a
constant, $\beta=\mathcal{O}(z\log z)$, and $\delta<1/4$.

###  4.3 UDGs and USGs with Other Norms

Let $G=(V,E)$ be a UDG corresponding to a set of points $V$ in the plane.
Recall that for $u,v\in V$, there is an edge $\\{u,v\\}\in E(G$) iff
$||u-v||_{2}\leq 2$. In the euclidean edge-weighted UDG, we defined the weight
of this edge to also be $||u-v||_{2}$. However, it is possible to define the
weights to be the $\ell_{p}$ distance between the points for arbitrary $p\geq
1$. To show that $\ell_{p}$-weighted UDGs satisfy the Locally Euclidean
property, we can use arguments similar to the $\ell_{\infty}$-weighted USG
case. We omit the details.

Planar Spanner. Consider the spanner $H^{\prime}$ obtained by applying
Proposition 6 to $G^{\prime}$, where $G^{\prime}$ is the euclidean (i.e.,
$L_{2}$) weighted UDG corresponding to the set of points $V$. follows that for
any $u,v\in V$,
$\mathsf{d}_{G^{\prime}}(u,v)\leq\mathsf{d}_{H^{\prime}}(u,v)\leq
2.42\cdot\mathsf{d}_{G^{\prime}}(u,v)$. In particular, for any edge $u,v\in
E(G)$, $||u-v||_{2}\leq\mathsf{d}_{H^{\prime}}(u,v)\leq 2.42\cdot||u-v||_{2}$.

First, consider the case when the weights in $G$ are given by the $L_{p}$ norm
distances between the points, where $1\leq p<2$. From 3, it follows that
$\mathsf{d}_{G}(u,v)=||u-v||_{p}\leq||u-v||_{2}\leq\mathsf{d}_{H^{\prime}}(u,v)\leq
2.42\cdot||u-v||_{2}\leq 2.42\cdot\sqrt{2}\cdot||u-v||_{p}$. It follows that
for any $u^{\prime},v^{\prime}\in G$,
$\mathsf{d}_{G}(u^{\prime},v^{\prime})\leq\mathsf{d}_{H^{\prime}}(u^{\prime},v^{\prime})\leq
3.42\cdot\mathsf{d}_{G}(u^{\prime},v^{\prime})$.

Otherwise, the weights in $G$ are given by $L_{p}$ norm distances, where
$2<p\leq\infty$. Then, let $H$ be the weighted graph obtained by multiplying
the weight of each edge in the spanner $H^{\prime}$ by a factor of $\sqrt{2}$.
Note that for any edge $\\{u,v\\}\in E(G)$, 3 implies that
$||u-v||_{p}\leq\sqrt{2}\cdot||u-v||_{2}\leq\sqrt{2}\cdot||u-v||_{p}$. This
implies that, for $\\{u,v\\}\in E(G)$,
$\mathsf{d}_{G}(u,v)=||u-v||_{p}\leq\sqrt{2}||u-v||_{2}\leq\sqrt{2}\cdot\mathsf{d}_{H^{\prime}}(u,v)=\mathsf{d}_{H}(u,v)\leq
2.42\cdot\sqrt{2}\cdot\sqrt{2}\cdot||u-v||_{p}$. This implies that for any
$u^{\prime},v^{\prime}\in V$, it holds that
$\mathsf{d}_{G}(u,v)\leq\mathsf{d}_{H}(u^{\prime},v^{\prime})\leq
4.84\cdot\mathsf{d}_{G}(u,v)$.

In either case, we conclude that Proposition 6 can be used to show the
existence of an $\alpha$-stretch planar spanner, where $\alpha\leq 4.84$.

From the above discussion, it follows that $\ell_{p}$-weighted UDGs also
satisfy the two properties required to apply our framework. Finally, it is
easy to modify the previous arguments to also show that $\ell_{p}$-weighted
USGs satisfy the canonical geometric properties. Thus, we conclude the
following theorem.

######  Theorem 7.

Consider the metric space $(V,\mathsf{d}_{G})$ induced by any
$\ell_{p}$-weighted UDG (resp. $\ell_{p}$-weighted USG) $G=(V,E)$ for some
$1\leq p\leq\infty$, a set $P\subseteq V$ with $n$ distinct points, and two
positive integers $k$ and $z$. Then there exists a polynomial-time algorithm
that constructs with probability at least $1-\delta$ a coreset for
$(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k\log^{3}(1/\delta))$, where $z$ and
$\beta$ are constants, and $\delta<1/4$.

###  4.4 Unweighted Unit Disk Graphs with Bounded Degree

Here, we consider metrics induced by _unweighted_ UDGs. That is, if $G=(V,E)$
is a Unit Disk Graph, then for any two vertices $u,v\in V(G)$, the distance
$\mathsf{d}_{G}(u,v)$ is given by the _hop-length_ $|\pi_{G}(u,v)|$ of a
shortest path $\pi_{G}(u,v)$. Note two points that are very close to each
other in an embedding of $G$, are still are at distance $1$ apart according to
the hop metric. Therefore, unweighted UDGs do not satisfy Locally Euclidean
property. However, they do admit a constant stretch planar spanner, as noted
below. In the following, we show that the arguments relying on the locally
euclidean properties can be modified for unweighted UDGs, when the maximum
degree is upper bounded by $\Delta$. Consequently, the size of the coreset we
construct, then, will depend on $\Delta$.

Let $G=(V,E)$ be an unweighted UDG. First, we observe that the distance
between any pair of vertices is given by the hop-length of the shortest path
between them, and thus is always a non-negative integer. Furthermore,
$\mathsf{d}_{G}(u,v)=0$ iff $u=v$; otherwise $\mathsf{d}_{G}(u,v)\geq 1$.

By examining the proof of the centroid set theorem, we observe the following.
Locally Euclidean property is used to construct the sets
$\mathbb{C}_{\text{net}}$, and $\mathbb{C}_{\text{support}}$, and Planar
Spanner property is used to construct the set $\mathbb{C}_{\text{landmark}}$.
Finally, the centroid set $\mathbb{C}$ is defined as the union of the three
sets $\mathbb{C}_{\text{net}},\mathbb{C}_{\text{support}}$, and
$\mathbb{C}_{\text{landmark}}$. In the following, we adapt the construction of
$\mathbb{C}$ for the unweighted UDGs.

First, we make use of the following result.

######  Proposition 7 ([7]).

For any unweighted UDG $G^{\prime}$, there exists a planar spanner
$H^{\prime}$ for hop-distances in $G^{\prime}$. That is, for any $u,v\in
V(G^{\prime})$,
$\mathsf{d}_{G^{\prime}}(u,v)\leq\mathsf{d}_{H^{\prime}}(u,v)\leq\alpha\cdot\mathsf{d}_{G^{\prime}}(u,v)$
for some absolute constant $\alpha\geq 1$.

Note that the stretch factor $\alpha$ is an absolute constant, and this result
_does not_ require that the maximum degree of the UDG is bounded. Following
this, we let $\ell\coloneqq\alpha/\epsilon$. We construct the set
$\mathbb{C}_{\text{landmark}}$ exactly as in the original construction using
the recursive decomposition and the planar spanner.

We define $\mathbb{C}_{\text{net}}\coloneqq\emptyset$, and construct
$\mathbb{C}_{\text{support}}$ as follows. For every point $p\in X$, we add
_all_ vertices within $\ell$ hops from $p$ in $G$ to the set
$\mathbb{C}_{\text{support}}$. Alternatively, this can be viewed as an
alternative to Proposition 4 to construct a bounded degree support graph,
namely the support graph $H$ is equal to $G$, and $f:V(G)\to V(H)$ being the
identity mapping. The only caveat is that the degree of $H$ is bounded by
$\Delta$, rather than $\mathcal{O}(1/\mu^{2})$ as required in the original
definition. Finally, let
$\mathbb{C}=\mathbb{C}_{\text{landmark}}\cup\mathbb{C}_{\text{support}}$. We
have the following observation.

######  Claim 8.

$|\mathbb{C}|=\exp\left(\mathcal{O}\left(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|+\log\Delta\right)\right)$

###### Proof.

Since $\mathbb{C}_{\text{landmark}}$ is constructed in exactly the same manner
as before, we can use the same upper bound as in the proof of Lemma 5.
That is,
$|\mathbb{C}_{\text{landmark}}|=\exp\left(\log^{2}|X|+z^{16}\epsilon^{-8}(\log(z/\epsilon))^{8}\log|X|\right)$.

Now we separately bound $|\mathbb{C}_{\text{support}}|$. Consider a
realization of $G$ in the plane. We overlay a grid of sidelength $1$ on the
plane. Note that any two points that lie in the same grid cell must have an
edge between them. Since the maximum degree of $G$ is $\Delta$, it follows
that every cell contains at most $\Delta$ vertices of $V(G)$. Let $H$ denote
the Furthermore, if $\\{u,v\\}\in E(G)$, then the euclidean distance between
the centers of the cells containing $u$ and $v$ respectively, is at most $3$.

Now consider a point $p\in X$, and any vertex $q$ such that
$\mathsf{d}_{G}(p,q)\leq\ell$. It follows that the euclidean distance between
centers of the cells containing $p$ and $q$ is at most $3\ell$. Therefore, $q$
can belong to one of at most $\pi(3\ell)^{2}=\mathcal{O}(\ell^{2})$ cells
satisfying this condition. Since each of the cells contains at most $\Delta$
points of $V(G)$, and $\ell=\mathcal{O}(z/\epsilon)$, we add at most
$\mathcal{O}(z^{2}\Delta/\epsilon^{2})$ points to
$\mathbb{C}_{\text{support}}$ for every point $p\in X$, which implies that
$|\mathbb{C}_{\text{support}}|=\mathcal{O}(|X|\cdot
z^{2}\Delta/\epsilon^{2})$. ∎

Now we discuss the modifications required to construct $\tilde{s}$ and in the
error analysis. Consider some $s\in\mathcal{S}$. If
$s\in\mathbb{C}_{\text{support}}$, then we let $\tilde{s}=s$, and add it to
$\tilde{\mathcal{S}}$. Clearly,
$\mathsf{d}_{G}(p,s)=\mathsf{d}_{G}(p,\tilde{s})$. Otherwise, it follows that
for all points $p\in X$, $\mathsf{d}_{G}(p,s)>\ell$. Then, we use recursive
decomposition and case analysis to find a point
$\tilde{s}\in\mathbb{C}_{\text{landmark}}$ that has same rounded distances
w.r.t. a landmark set $\mathcal{L}(\cdot)$ as in the original proof. Then,
using similar analysis, we can show that for any $p\in X_{s}$, it holds that
$\mathsf{cost}(p,\tilde{\mathcal{S}})\leq(1+\epsilon)\cdot\mathsf{cost}(p,\mathcal{S})+\epsilon\cdot\mathsf{cost}(p,\mathcal{A})$.
We omit the details, and conclude with the following theorem.

######  Theorem 8.

Consider the metric space $(V,\mathsf{d}_{G})$ induced by an unweighted UDG
$G=(V,E)$ with maximum degree $\Delta$, a set $P\subseteq V$ with $n$ distinct
points, and two positive integers $k$ and $z$. Then there exists a polynomial-
time algorithm that constructs with probability at least $1-\delta$ a coreset
for $(k,z)$-clustering on $P$ of size
$\mathcal{O}(\epsilon^{-\beta}k\log^{2}k\log^{3}(1/\delta)+\log(\Delta))$,
where $z$ and $\beta$ are constants, and $\delta<1/4$.

##  5 Constant Stretch Planar Spanner for Unit Square Graphs

In this section we prove Theorem 5.

Preliminaries. For points $p=(x_{p},y_{p}),q=(x_{q},y_{q})\in^{2}$, let
$\Delta_{x}(p,q)=|x_{p}-x_{q}|$ and $\Delta_{y}(p,q)=|y_{p}-y_{q}|$, and
$D(p,q)=||p-q||_{\infty}=\max\\{\Delta_{x}(p,q),\Delta_{y}(p,q)\\}$, and
$\delta(p,q)=\min\\{\Delta_{x}(p,q),\Delta_{y}(p,q)\\}$. For points $p$ and
$q$, we use $\overline{pq}$ (or $\overline{qp})$ to denote the (closed) line
segment between $a$ and $b$. We denote the (euclidean) length of the segment
$\overline{pq}$ by $|pq|$.

In the following, whenever we say _square_ or a _rectangle_ , we always refer
to an _axis-parallel square_ or an _axis-parallel rectangle_ , along with its
interior (unless explicitly mentioned otherwise). We denote the sidelength of
a square $S$ by $\ell(S)$. A _unit square_ centered at a point
$p=(x_{p},y_{p})$, is $S(p)\coloneqq\\{q=(x_{q},y_{q}):D(p,q)\leq 1\\}$. Note
that $\ell(S(p))=2$. Note that for any point $q$ lying on the boundary of
$S(p)$, it holds that $D(p,q)=1$. For convenience, we refer to the four sides
of the square corresponding to the cardinal directions as N, E, S, W
respectively. For a pair of points $a,b$ such that $\overline{ab}$ is not
axis-parallel, we use $R(a,b)$ to denote an axis-parallel rectangle that has
$a$ and $b$ as the endpoints of a diagonal.

The following two propositions can be proved via elementary geometry and
properties of $\ell_{\infty}$ distances.

######  Proposition 8.

Let $a=(x_{a},y_{a})$ and $b=(x_{b},y_{b})$ be arbitrary and distinct points
in 2. Let $S$ be any square having $a$ and $b$ on its boundary. Then,
$\ell(S)\geq D(a,b)$.

######  Proposition 9.

Let $a$ and $b$ be two distinct points in the plane such that $\overline{ab}$
is not parallel to $x$ or $y$ axis. Then, for any point $c$ lying on or inside
$R(a,b)$, the following holds: $D(a,c)\leq D(a,b)$ and $D(b,c)\leq D(a,b)$.

We follow the construction of Binichon et al. [8], and show that the
$\ell_{\infty}$ Delaunay Triangulation, when restricted to USG edges, remains
a constant stretch spanner for the corresponding USG.

Fix a set of points $P$. We make the general position assumption, namely, no
four points of $P$ lie on the boundary of an axis-parallel square.
Furthermore, by slightly perturbing the set of points if necessary, we assume
that all pairwise $L_{\infty}$ distances are unique. Under this assumption,
the $\ell_{\infty}$ Delaunay triangulation is unique and planar. If $pq$ is an
edge in the Delaunay Triangulation $T$, we say that $pq$ is a _DT_ edge.
Finally, let $H$ be a subgraph of USG on $P$, defined as follows: for $p,q\in
P$, $pq\in E(H)$ iff $pq$ is a DT edge _and_ $pq\in E(G)$, i.e., $pq$ is an
USG edge. Furthermore, the length of each edge $pq\in E(H)$ is set to be
$D(pq)$, i.e., if $pq\in E(H)$, then
$\mathsf{d}_{H}(p,q)=\mathsf{d}_{G}(p,q)=D(p,q)$.

In the following, we show the following key lemma.

######  Lemma 6.

Let $a=(x_{a},y_{a})$ and $b=(x_{b},y_{b})$ be two points in $P$ such that
$ab\in E(G)$.
Then, there exists a path $\pi_{H}(a,b)=(a=v_{0},v_{1},\ldots,v_{t}=b)$ in $H$
satisfying the following properties.

  * •

$\mathsf{d}_{H}(a,b)\leq\sum_{i=1}^{t}\mathsf{d}_{H}(v_{i-1},v_{i})\leq
2D(a,b)+\delta(a,b)\leq 3\cdot\mathsf{d}_{G}(a,b)$, and

  * •

For every $1\leq i\leq t$, $D(v_{i-1},v_{i})=\mathsf{d}_{H}(v_{i-1},v_{i})\leq
D(ab)$.

In the following, we fix a pair of points $a,b\in P$ such that $ab$ is not an
edge, and follow a geometric construction from [8] using the Delaunay
triangulation of points. We will perform a more careful analysis of this set
of points so that subsequently these properties can be used later to prove
Lemma 6.

We proceed as in [8] and let $a=(0,0)$ and $b=(w,h)$ be a pair of points, such
that $ab$ is not a DT edge. Here, we assume that $0\leq h\leq w$ and $0<w$.
Thus, note that $D(a,b)=w\geq h$. Let $T_{1},T_{2},\ldots,T_{k}$ be the
sequence of triangles that $\overline{ab}$ intersects when moving from $a$
towards $b$. Suppose the rectangle $R(a,b)$ contains no point of $P$ other
than $a$ and $b$. Let $h_{0}=l_{0}=a$. For each triangle $T_{i}$, $1\leq i\leq
k$, the segment $\overline{ab}$ intersects the sides of $T_{i}$ twice. Let
$h_{i}$ and $l_{i}$ be the endpoints of the sides of $T_{i}$ _last_ , while