ptimal Spanners for Unit Ball Graphs in Doubling Metric

Resolving an open question from 2006 @damian2006local, we prove the existence of light-weight bounded-degree spanners for unit ball graphs in the metrics of bounded doubling dimension, and we design a simple $\mathcal{O}(\log^*n)$-round distributed algorithm that given a unit ball graph $G$ with $n$ vertices and a positive constant $\epsilon < 1$ finds a $(1+\epsilon)$-spanner with constant bounds on its maximum degree and its lightness using only 2-hop neighborhood information. This immediately improves the algorithm of Damian, Pandit, and Pemmaraju @damian2006distributed which runs in $\mathcal{O}(\log^*n)$ rounds but has a $\mathcal{O}(\log \Delta)$ bound on its lightness, where $\Delta$ is the ratio of the length of the longest edge in $G$ to the length of the shortest edge. We further study the problem in the two dimensional Euclidean plane and we provide a construction with similar properties that has a constant average number of edge intersection per node. This is the first distributed low-intersection topology control algorithm to the best of our knowledge. Our distributed algorithms rely on the maximal independent set algorithm of Schneider and Wattenhofer @schneider2008log that runs in $\mathcal{O}(\log^*n)$ rounds of communication. If a maximal independent set is known beforehand, our algorithms run in constant number of rounds.

Introduction
============

Given a collection of points $V$ in a metric space with doubling dimension $d$, the weighted *unit ball graph (UBG)* on $V$ is defined as a weighted graph $G(V, E)$ where two points $u, v\in V$ are connected if and only if their metric distance $\lVert uv\rVert\leq 1$. The weight of the edge $uv$ of the UBG is $\lVert uv\rVert$ if the edge exists. Unit ball graphs in the Euclidean plane are called unit disk graphs (UDGs) and are frequently used to model ad-hoc wireless communication networks, where every node in the network has an effective communication range $R$, and two nodes are able to communicate if they are within a distance $R$ of each other.

The necessity of a connected and energy-efficient topology for high-level routing protocols led researchers to develop many spanning algorithms for ad-hoc networks and in particular, UDGs. But the decentralized nature of ad-hoc networks demands that these algorithms be local instead of centralized. In these applications, it is important that the resulting topology is connected, has a low weight, and has a bounded degree, implying also that the number of edges is linear in the number of vertices.

Several known *proximity graphs* have been studied for this purpose, including the relative neighborhood graph (RNG), Gabriel graph (GG), Delaunay graph (DG), and Yao graph (YG). It is well-known that these proximity graphs are sparse and they can be calculated locally, using only the information from a node's neighborhood. But further analysis shows that they have poor bounds on at least one of the important criteria: maximum vertex degree, total weight, and stretch-factor @li2001power.

Therefore, researchers modified these constructions to fulfill these requirements. Li, Wan, and Wang @li2001power introduced a modified version of the Yao graph to resolve the issue of unbounded in-degree while preserving a small stretch-factor, but they left as an open question whether there exists a construction whose total weight is also bounded by a constant factor of weight of the minimum spanning tree. The localized Delaunay triangulation (LDT) @li2003localized and local minimum spanning tree (LMST) @li2005design were two other efforts in this way which failed to bound the total weight of the spanner.

In 2006, Damian, Pandit, and Pemmaraju @damian2006local designed a distributed construction that satisfied all the desired properties for UBGs lying in *$d$-dimensional Euclidean space*. But they used the so-called *leapfrog property* to prove the $\mathcal{O}(1)\omega(MST)$ bound on the weight of the spanner, which does not hold for the spaces of bounded doubling dimension in general. Instead, they showed in another work @damian2006distributed that the weight of their spanner in the spaces of bounded doubling dimension is bounded by $\mathcal{O}(\Delta)\omega(MST)$, where $\Delta$ is the ratio of the length of the longest edge in the graph divided by the length of its smallest edge.

Since then, it has remained open whether UBGs in the spaces of bounded doubling dimension possess a $(1+\epsilon)$-spanner with constant bounds on the maximum degree and lightness of the spanner. Apart from being a generalization of the Euclidean space, the importance of the spaces of bounded doubling dimension comes from the fact that a small perturbation in the distances does not affect the doubling dimension by much, while it can change the Euclidean dimension significantly, or the resulting distances might not even be embeddable in such metrics at all @chan2009small. This makes these metrics to be a more realistic model for real-world applications.

Contributions
-------------

In this paper we resolve this question that has remained open for more than a decade, and we prove the existence of light-weight bounded-degree $(1+\epsilon)$-spanners of unit ball graphs in the spaces of bounded doubling dimension. Our construction has constant bounds on the maximum degree and the lightness, and it can be built locally in $\mathcal{O}(\log^* n)$ rounds of communication, where $n$ is the number of vertices. Moreover, we modify this construction for the two dimensional Euclidean plane in order to have a linear number of edge intersections in total, implying a constant average number of edge intersection per node. To the best of our knowledge, this is the first distributed low-stretch low-intersection construction for unit disk graphs.

More specifically, we introduce a centralized algorithm that,

We also provide the distributed construction of a spanner with the same properties in ,

Furthermore, we study the problem in the case of the two dimensional Euclidean plane, where the greedy spanner on a complete weighted graph is known to have constant upper bounds on its lightness @filtser2016greedy, maximum degree, and average number of edge intersections per node @eppstein2020edge. We observe that a simple change on the this algorithm can extend these results for unit disk graphs as well. We call this modified algorithm and we show that

Finally we propose , a specific distributed low-intersection construction for the case of the two dimensional Euclidean plane that preserves the previously mentioned properties.

Preliminaries
=============

Doubling metrics
----------------

We start by recalling the definition of the doubling dimension of a metric space,

\[Doubling Dimension\] The doubling dimension of a metric space is the smallest $d$ such that for any $R>0$, any ball of radius $R$ can be covered by at most $2^d$ balls of radius $R/2$.

We say a metric space has *bounded doubling dimension* if its doubling dimension is upper bounded by a constant. Besides the triangle inequality, which is intrinsic to metric spaces, the *packing lemma* is an essential tool for the metrics of bounded doubling dimension. This lemma states that it is impossible to pack more than a certain number of points in a ball of radius $R>0$ without making a pair of points' distance less than some $r>0$.

\[Packing Property\] In a metric space of bounded doubling dimension $d$, let $X$ be a set of points with minimum distance $r$, contained in a ball of radius $R$. Then $|X|\leq \left(\frac{4R}{r}\right)^d$.

This is a well-known fact, see e.g. @smid2009weak.

Spanners for complete graphs
----------------------------

For a weighted graph $G$ in a metric space, where every edge weight is equal to the metric distance of its endpoints, a $t$-spanner is defined in the following way,

\[$t$-spanner\] A $t$-spanner of a weighted graph $G$ is a subgraph $S$ of $G$ that for every pair of vertices $x,y$ in $G$, $${\operatorname{dist}}_S(x,y)\leq t\cdot {\operatorname{dist}}_G(x,y)$$ where ${\operatorname{dist}}_A(x,y)$ is the length of a shortest path between $x$ and $y$ in $A$.

In other words, a $t$-spanner approximates the pairwise distances within a factor of $t$. Spanners were studied for complete weighted graphs first, and several constructions were proposed to optimize them with respect to the number of edges and total weight. Among these constructions, *greedy spanners* @althofer1990generating are known to out-perform the others.

A greedy spanner can be constructed by running the greedy spanner algorithm () on a set of points $V$ in a metric space. This short procedure adds edges one at a time to the spanner it constructs, in ascending order by length. For each pair of vertices, in this order, it checks whether the pair already satisfies the distance inequality using the edges already added. If not, it adds a new edge connecting the pair. Therefore, by construction, each pair of vertices satisfies the inequality, either through previous edges or (if not) through the newly added edge. The resulting graph is therefore a $t$-spanner.

\[ht\]

\[1\] Let $S$ be a graph with vertices $V$ and edges $E=\{\}$ Add edge $PQ$ to $E$S

Despite the simplicity of , Farshi and Gudmundsson @farshi2005experimental observed that in practice, greedy spanners are surprisingly good in terms of the number of edges, weight, maximum vertex degree, and also the number of edge crossings in the two dimensional Euclidean plane. All of these properties have been proven rigorously so far. Filster and Solomon @filtser2016greedy proved that greedy spanners have size and lightness that is optimal to within a constant factor for worst-case instances. They also achieved a near-optimality result for greedy spanners in spaces of bounded doubling dimension. Borradaile, Le, and Wulff-Nilsen @borradaile2019greedy recently proved optimality for doubling metrics, generalizing a result of Narasimhan and Smid @narasimhan2007geometric, and resolving an open question posed by Gottlieb @gottlieb2015light, and Le and Solomon showed that no geometric $t$-spanner can do asymptotically better than the greedy spanner in terms of number of edges and lightness @le2019truly.

In a recent work, the authors of this paper showed that the number of edge crossings of the greedy spanner in the two dimensional Euclidean plane is linear in the number of vertices @eppstein2020edge. Moreover, they proved that the crossing graph of the greedy spanner has bounded degeneracy, implying the existence of sub-linear separators for these graphs @eppstein2017crossing. This, together with the well-known fact that greedy spanners have bounded-degree in the two dimensional Euclidean plane, makes greedy spanners more practical in this particular metric space.

Although the degree of the greedy spanner is bounded in the two dimensional Euclidean plane, it is known that there exist $n$-point metric spaces with doubling dimension 1 where the greedy spanner has maximum degree $n-1$ @filtser2016greedy. Gudmundsson, Levcopoulos, and Narasimhan @gudmundsson2002fast devised a faster algorithm that was later proven to have bounded degree as well as constant lightness and linear number of edges @filtser2016greedy. We call this algorithm in this paper, and we make use of it in our algorithms for the metrics of bounded doubling dimension, while we take advantage of the extra low-intersection property of in the two dimensional Euclidean plane.

Unit ball graphs
----------------

We formally define a unit ball graph on a set of points $V$ in the following way,

\[Unit Ball Graph\] Given a set of points $V$ in a metric space, the unit ball graph $G$ on $V$ contains $V$ as its vertex set and every two vertices $x,y\in V$ are connected if and only if $\lVert xy\rVert\leq 1$. The weight of an edge $(x,y)$ is equal to $\lVert xy\rVert$ if the edge exists.

Unit ball graphs are an important subclass of the graphs called *growth-bounded graphs*, which only limit the number of independent nodes in every neighborhood, a property that holds for UBGs due to the packing property.

Schneider and Wattenhofer presented a $\mathcal{O}(\log^* n)$-round distributed algorithm for finding a maximal independent set (MIS) of a growth-bounded graph in a space with bounded doubling dimension @schneider2008log. Throughout the paper we refer to their algorithm by . It turns out that will be a key ingredient of our distributed algorithms, as well as their bottleneck in terms of the number of rounds. This means that if a maximal independent set is known beforehand, our algorithms can be executed fully locally, in constant number of rounds.

In we prove the existence of $(1+\epsilon)$-spanners with constant bounds on the maximum degree and the lightness by introducing an algorithm that finds such spanners in a centralized manner. In we propose a distributed construction that delivers the same features through a $\mathcal{O}(\log^* n)$-round algorithm. Finally, in we consider the special case of two dimensional Euclidean plane and we design centralized and distributed algorithms to construct a spanner that has the extra low-intersection property, making it more suitable for practical purposes.

Centralized construction {#sec:central}
========================

In this section we propose a centralized construction for a light-weight bounded-degree $(1+\epsilon)$-spanner for unit ball graphs in a metric of bounded doubling dimension. Later in we use this centralized construction to design a distributed algorithm that delivers the same features.

It is worth mentioning that the greedy spanner would be a $(1+\epsilon)$-spanner of the UBG if the algorithm stops after visiting the pairs of distance at most 1, and it even has a weight of $\mathcal{O}(1)\omega(MST)$, but as we mentioned earlier, there are metrics with doubling dimension 1 in which its degree may be unbounded.

So instead, in Algorithm \[alg:centralgreedy\] we use a combination of the algorithm of @gudmundsson2002fast, called , and a modified version of the refinement technique from Peleg and Roditty @peleg2010localized, which removes the edges of length larger than 1 from the spanner and replaces them with three smaller edges to make the output a subgraph of the UBG. We use a modified version of this refinement because the original version can lead to vertices having unbounded degrees. It is proven in @narasimhan2007geometric that has the desired properties for Euclidean metrics, but as stated in @filtser2016greedy, the proof only relies on the triangle inequality and packing argument which both work for doubling metrics as well. Therefore, we may safely assume that finds a light-weight bounded-degree $(1+\epsilon)$-spanner of the complete weighted graph defined on the point set.

The algorithm
-------------

In the first step of the algorithm () we choose $\epsilon'=\epsilon/36$, a smaller stretch parameter than $\epsilon$, to cover the errors that future steps might inflict to the spanner. Then we call the procedure on the set of vertices $V$ to calculate a light-weight bounded-degree $(1+\epsilon')$-spanner $S$ of the complete weighted graph on $V$. This spanner might contain edges of length larger than 1, which we will replace by some edges of length at most 1 in the future steps.

Since an edge of length larger than $1+\epsilon'$ in $S$ cannot participate in the shortest path between any two adjacent vertices in $G$, we simply remove and discard them from the spanner. Then for every remaining edge $e=(u,v)$ of length in the range $(1,1+\epsilon']$ we find an edge $(x,y)$ of the original graph $G$ so that $\lVert ux\rVert \leq \epsilon'$ and $\lVert vy\rVert \leq \epsilon'$. We then replace such edge $e$ by the edge $(x,y)$. We call the pair $(x,y)$ the *replacement edge* or the *replacement pair* for the edge $e$. Since this procedure can end up assigning too many replacement edges to a single vertex ($x$ or $y$ in this case) and hence increasing its degree significantly, we perform a simple check before adding a replacement edge; we store the set $R$ of previously added replacement pairs in the memory and if a *weak* replacement pair $(x',y')\in R$ exists, then we prefer it over a newly found replacement pair $(x,y)\notin R$. By weak replacement pair we mean a pair $(x',y')\in R$ that $\lVert ux'\rVert \leq 2\epsilon'$ and $\lVert vy'\rVert \leq 2\epsilon'$, which is weaker than the definition of the replacement pair. As we later see this weaker notion of replacement pair will help us to bound the degree of the vertices.

After removing the edges of length larger than 1 and replacing the ones in the range $(1,1+\epsilon']$, we return the spanner to the output.

\[ht\]

**Input.** A unit ball graph $G(V,E)$ in a metric with doubling dimension $d$.\
**Output.** A light-weight bounded-degree $(1+\epsilon)$-spanner of $G$.

\[1\]$\epsilon'\gets \epsilon/36$ $S \gets$ R $\gets\varnothing$ Remove $e$ from $S$$S\gets S\cup \{(x,y)\}$$R\gets R\cup \{(x,y)\}$ S

The analysis
------------

Now we prove that the output $S$ of the algorithm is a light-weight bounded-degree $(1+\epsilon)$-spanner of the unit ball graph $G$. Clearly, after the refinement is done the spanner $S$ is a subgraph of $G$, so we need to analyze the lightness, the stretch factor, and the maximum degree of the spanner.

First we prove that the stretch-factor of the spanner is indeed bounded by $1+\epsilon$.

The spanner returned by has a stretch factor of $1+\epsilon$.\[lem:cen-str\]

We recall that the output of is a light-weight bounded-degree $(1+\epsilon')$-spanner of the complete weighted graph on the point set. So an edge $e$ of length $|e|>1+\epsilon'$ cannot be used to approximate any edges in the UBG, i.e. if $(x,y)\in E$ then $e$ cannot belong to the shortest path between $x$ and $y$ in $S$; otherwise the length of the path would exceed $1+\epsilon'$ which cannot happen. So we may safely remove these edges in the first step of the refinement procedure.

Also, any edge of length in the range $(1,1+\epsilon']$ that is not used in a shortest path between any two endpoints of an edge of UBG can be removed as well, because removing them does not change the stretch-factor of the spanner. Now consider an edge $(x,y)$ of the UBG that uses a spanner edge $e\in S$ that $|e|\in(1,1+\epsilon']$ on its shortest path. We want to prove that after the replacement of $e$, the shortest path between $x$ and $y$ remains within $1+\epsilon$ factor of their distance. Clearly, we have $\lVert ux\rVert\leq \epsilon'$ and $\lVert vy\rVert\leq \epsilon'$; otherwise the length of the path $xuvy$ would be more than $1+\epsilon'$, contradicting the fact that it is approximating an edge of length at most 1. This shows that $(x,y)$ would be a valid replacement edge for $e$. So we can safely assume that the algorithm finds a replacement edge $(x',y')\in E$ for $e$. This replacement edge might be a normal replacement edge or a weak replacement edge, either way, we have $\lVert ux'\rVert \leq 2\epsilon'$ and $\lVert vy'\rVert\leq 2\epsilon'$. By the triangle inequality $$\lVert x'x\rVert \leq \lVert x'u\rVert + \lVert ux\rVert \leq 2\epsilon' + \epsilon' = 3\epsilon'$$ Similarly, $\lVert yy'\rVert \leq 3\epsilon'$. Therefore $$\label{eq:cen-eq1}
    \lVert x'y'\rVert \leq \lVert x'x\rVert + \lVert xy\rVert + \lVert yy'\rVert
    \leq \lVert xy\rVert + 6\epsilon'$$ Denote the shortest spanner path between $x$ and $x'$ by $P_{xx'}$ and similarly define $P_{yy'}$. Consider the spanner path $P=P_{xx'}x'y'P_{y'y}$ that connects $x$ and $y$. Using the length of the path $P$ is $$\label{eq:cen-eq2}
    |P|=|P_{xx'}| + \lVert x'y'\rVert + |P_{y'y}| \leq \lVert xy\rVert + 6\epsilon' + |P_{xx'}| + |P_{y'y}|$$ The changes that we make in the refinement process do not affect the length of short paths like $P_{xx'}$ and $P_{y'y}$. So we have $$|P_{xx'}|\leq (1+\epsilon')\lVert xx'\rVert\leq 3\epsilon'(1+\epsilon')$$ Similarly, $|P_{yy'}|\leq 3\epsilon'(1+\epsilon')$. Putting these into and using $\epsilon=36\epsilon'$, $$\label{eq:cen-eq3}
    |P|\leq \lVert xy\rVert + 6\epsilon' + 6(1+\epsilon')\epsilon' \leq \lVert xy\rVert + \frac{\epsilon}{1+\epsilon'}$$ But since $e$ was previously approximating the edge $(x,y)$, we know that $(1+\epsilon')\lVert xy\rVert \geq |e| > 1$ or equivalently $\lVert xy\rVert > 1/(1+\epsilon')$. Substituting this into , $$|P|\leq \lVert xy\rVert+\epsilon\lVert xy\rVert  = (1+\epsilon)\lVert xy\rVert$$ So $S$ is a $(1+\epsilon)$-spanner of $G$.

Now we analyze the weight of the spanner, proving its constant lightness.

The spanner returned by has a weight of $\mathcal{O}(1)\omega(MST)$.\[lem:cen-light\]

Again, we use the fact that the output of has weight $\mathcal{O}(1)\omega(MST(G))$. During the refinement process, every edge is replaced by an edge of smaller length, so the whole weight of the graph does not increase during the refinement process. Therefore in the end $\omega(S) = \mathcal{O}(1)\omega(MST(G))$.

As the final step, we bound the maximum degree of the spanner.

The spanner returned by has bounded degree.\[lem:cen-deg\]

It is clear from the algorithm that immediately after processing an edge $e=(u,v)$, the degree of $u$ and $v$ does not increase; it may decrease due to the removal of the edge which is fine. But if a replacement edge $(x,y)$ is added after the removal of $e$ then the degree of $x$ and $y$ is increased by at most 1. We need to make sure this increment is bounded for every vertex.

Let $x$ be an arbitrary vertex of $G$ and let $(x,y)$ and $(x,z)$ be two replacement edges that have been added to $x$ in this order as a result of the refinement process. We claim that $\lVert yz\rVert > \epsilon'$ holds. Assume, on the contrary, that $\lVert yz\rVert \leq \epsilon'$, and also assume that $(x,z)$ has been added in order to replace an edge $(u,v)$ of the spanner. Then by the triangle inequality $$\lVert vy\rVert \leq \lVert vz\rVert + \lVert zy\rVert \leq 2\epsilon'$$ Also $\lVert ux\rVert \leq \epsilon' < 2\epsilon'$ because $(x,z)$ is added to replace $(u,v)$. But the last two inequalities contradict the fact that $(x,y)$ cannot be a weak replacement for $(u,v)$.

Now that we have proved $\lVert yz\rVert > \epsilon'$ we can use the packing property of the bounded doubling dimension to bound the number of such replacement edges around $x$. All the other endpoints of such replacement edges are included in ball of radius 1 around $x$, and the distance between every two such points is at least $\epsilon'$. Thus by the packing property there can be at most $(\frac{4}{\epsilon'})^d=\epsilon^{-\mathcal{O}(d)}$ many replacement edges incident to $x$.

Putting these together, we can finally prove .

\[Centralized Spanner\] \[thm:cen\]

Follows directly from Lemma \[lem:cen-str\], Lemma \[lem:cen-light\], and Lemma \[lem:cen-deg\].

Distributed construction {#sec:dist}
========================

For the distributed construction we propose Algorithm \[alg:localgreedy\]. There is a preprocessing step of finding a maximal independent set $I$ of $G$, which can be done using the distributed algorithm of @schneider2008log in $\mathcal{O}(\log^*n)$ rounds. We refer to this algorithm by . Then the subroutine from is run on every vertex $w\in I$ to find a $(1+\epsilon)$-spanner $S_w$ of the 2-hop neighborhood of $w$, denoted by $\mathcal{N}^2(w)$. At the final step, every $w\in I$ sends its local spanner edges to the corresponding endpoints of every edge. Symmetrically, every vertex listens for the edges sent by the vertices in $I$ and once a message is received, it stores the edges in its local storage. In other words, the final spanner is the union of all these local spanners. We use the centralized algorithm of for every local neighborhood $\mathcal{N}^2(w)$ to guarantee the bounds that we need.

\[ht\]

**Input.** A unit ball graph $G(V, E)$ in a metric with doubling dimension $d$ and an $\epsilon>0$.\
**Output.** A light-weight bounded-degree $(1+\epsilon)$-spanner of $G$.

\[1\]Find a maximal independent set $I$ of $G$ using @schneider2008logRun on the vertices of $G$Retrieve $\mathcal{N}^2(w)$, the 2-hop neighborhood information of $w$$\mathcal{S}_w \gets $ Send $e$ to $u$ and $v$Listen to incoming edges and store them

Now we show that the spanner introduced in Algorithm \[alg:localgreedy\] possesses the desired properties.

can be done in $\mathcal{O}(\log^*n)$ rounds of communication.\[lem:dis-rnd\]

The preprocessing step of finding the maximal independent set takes $\mathcal{O}(\log^*n)$ rounds of communication @schneider2008log. Retrieving the 2-hop neighborhood information can be done in $\mathcal{O}(1)$ rounds of communication. Computing the greedy spanner is done locally, and the edges are sent to their endpoints, which again can be done in $\mathcal{O}(1)$ rounds of communication. Overall, the algorithm requires $\mathcal{O}(\log^*n)$ rounds of communication.

The spanner returned by has a stretch factor of $1+\epsilon$.\[lem:dis-str\]

From we know that $\mathcal{S}_w$ is a light-weight bounded-degree $(1+\epsilon)$-spanner of $\mathcal{N}^2(w)$. Let $u,v\in V$ be chosen arbitrarily. We need to make sure there is a path of length at most $(1+\epsilon)d_G(u,v)$ between $u$ and $v$ in the output.

First we prove this for the case that $(u,v)\in E$. So let $e=(u,v)\in E$. Then $u$ is either in $I$ or has a neighbor in $I$, according to choice of $I$. In any case, the edge $e$ belongs to $\mathcal{N}^2(w)$ for some $w\in I$, which means that there is a path $P\subset \mathcal{S}_w$ of length at most $(1+\epsilon)|e|$ that connects $u$ and $v$. The edges of $P$ are all included in the final spanner according to the algorithm, so the output includes this path between $u$ and $v$, which has a length at most $(1+\epsilon)|e|$ and so the distance inequality is satisfied.

If $(u,v)\notin E$, we can take the shortest path $u=p_0,p_1,\cdots,p_k=v$ between them in $G$ and append the corresponding $(1+\epsilon)$-approximate paths $P_0,P_1,\cdots,P_{k-1}$ of the edges $p_0p_1, p_1p_2,\cdots, p_{k-1}p_k$, respectively, to get a $(1+\epsilon)$-approximate path for $p_0p_1\cdots p_k$. This implies that the stretch factor of the output is indeed $1+\epsilon$.

The spanner returned by has a bounded degree.\[lem:dis-deg\]

First we use the packing lemma to prove that any vertex $v\in V$ appears at most a constant number of times in different neighborhoods, $\mathcal{N}^2(w)$ for $w\in I$. Because $v\in \mathcal{N}^2(w)$ implies that $\lVert vw\rVert \leq 2$, any vertex $w\in I$ such that $v\in \mathcal{N}^2(w)$ should be contained in the ball of radius 2 around $v$. But all such $w$s are chosen from $I$, which is an independent set of $G$, so the distance between every two such vertex is at least 1. By the packing property, the maximum number of such vertices would be $8^d = \mathcal{O}(1)$.

Now that every vertex appears in at most in $8^d$ different sets $\mathcal{N}^2(w)$, for $w\in I$, and from we already knew that every vertex has bounded degree in any of $\mathcal{S}_w$s, it immediately follows that every vertex has bounded degree in the final spanner.

In order to bound the lightness of the output, we assume that $\epsilon\leq 1$ and we make a few comparisons. First, for any $w\in I$ we compare the weight of $\mathcal{S}_w$ to the weight of the minimum spanning tree on $\mathcal{N}^2(w)$. Then we compare the weight of the minimum spanning tree on $\mathcal{N}^2(w)$ to the weight of the minimum Steiner tree on $\mathcal{N}^3(w)$, where the required vertices are $\mathcal{N}^2(w)$ and 3-hop vertices are optional. Finally, we compare the weight of this minimum Steiner tree to the weight of the induced subgraph of on the subset of vertices $\mathcal{N}^3(w)$, which later implies that the overall weight of $\mathcal{S}_w$s is bounded by a constant factor of the weight of the minimum spanning tree on $G$.

Our first claim is that the weight of $\mathcal{S}_w$ is bounded by a constant factor of the weight of the MST on $\mathcal{N}^2(w)$.

$\omega(\mathcal{S}_w) = \mathcal{O}(1)\omega(MST(\mathcal{N}^2(w)))$\[cor:dis-cmp1\]

Follows from the properties of the centralized algorithm in .

Next we compare $\omega(MST(\mathcal{N}^2(w)))$ to the weight of the minimum Steiner tree of $\mathcal{N}^3(w)$ on the required vertices $\mathcal{N}^2(w)$.

Define $\mathcal{T}$ to be the optimal Steiner tree on the set of vertices $\mathcal{N}^3(w)$, where only vertices in $\mathcal{N}^2(w)$ are required and the rest of them are optional. Then\[lem:dis-cmp2\] $$\omega(MST(\mathcal{N}^2(w)))\leq 2\omega(\mathcal{T})$$

This is a well-known fact that implies a 2-approximation for minimum Steiner tree problem. The idea is if we run a full DFS on the vertices of $\mathcal{T}$ and we write every vertex once we open and once we close it, then we get a cycle whose shortcut on optional edges will form a path on the required vertices. The weight of the cycle is at least $\omega(MST(\mathcal{N}^2(w)))$ and at most $2\omega(\mathcal{T})$, which proves the result.

Finally, we compare the weight of $\mathcal{T}$ to the weight of induced subgraph of on the subset of vertices $\mathcal{N}^3(w)$.

Let $\mathcal{S}^*$ be the output of and let $\mathcal{S}^*_w$ be the induced subgraph of $\mathcal{S}^*$ on $\mathcal{N}^3(w)$. Then\[lem:dis-cmp3\] $$\omega(\mathcal{T}) \leq \omega(\mathcal{S}^*_w)$$

We prove that for $\epsilon\leq 1$, $\mathcal{S}^*_w$ forms a forest that connects all the vertices in $\mathcal{N}^2(w)$ in a single component. So $\mathcal{S}^*_w$ is a feasible solution to the minimum Steiner tree problem on the set of vertices $\mathcal{N}^3(w)$ with required vertices being $\mathcal{N}^2(w)$. Thus $\omega(\mathcal{T}) \leq \omega(\mathcal{S}^*_w)$.

Now we just need to prove that the vertices in $\mathcal{N}^2(w)$ are connected in $\mathcal{S}^*_w$. Let $u$ be an $i$-hop neighbor of $w$ and $v$ be an $i+1$-hop neighbor of $w$ for some $w\in I$ and $i=0,1$. Assume that $(u,v)\in E$. It is enough to prove that $u$ and $v$ are connected in $\mathcal{S}^*_w$. In order to do so, we observe that there is a path of length at most $(1+\epsilon)\lVert uv\rVert$ between $u$ and $v$ in $\mathcal{S}^*$. We show that this path is contained in $\mathcal{N}^3(w)$ and we complete the proof in this way, because $\omega(\mathcal{S}^*_w)$ is nothing but the induced subgraph of $\mathcal{S}^*$ on $\mathcal{N}^3(w)$.

Assume, on the contrary, that there is a vertex $x\notin \mathcal{N}^3(w)$ on the $(1+\epsilon)$-path between $u$ and $v$. This means that $x$ is not a 1-hop neighbor of any of $u$ and $v$, because otherwise $x$ would have been in $\mathcal{N}^3(w)$. So $\lVert ux\rVert>1$ and $\lVert vx\rVert>1$. Thus the length of the path would be at least $\lVert ux\rVert+\lVert xv\rVert>2\geq (1+\epsilon)\geq (1+\epsilon)\lVert uv\rVert$ which is a contradiction.

By putting together what we proved so far, we have

The spanner returned by has a weight of $\mathcal{O}(1)\omega(MST)$.\[prp:dis-light\]

By Corollary \[cor:dis-cmp1\], Lemma \[lem:dis-cmp2\], and Lemma \[lem:dis-cmp3\], $$\omega(\mathcal{S}_w) = \mathcal{O}(1)\omega(\mathcal{S}^*_w)$$ Summing up together these inequalities for $w\in I$, $$\omega(\text{output}) = \mathcal{O}(1)\sum_{w\in I}\omega(\mathcal{S}^*_w)$$ But remember that every vertex, and hence every edge of $\mathcal{S}^*$, is repeated $\mathcal{O}(1)$ times in the summation above, so $$\omega(\text{output}) = \mathcal{O}(1)\omega(\mathcal{S}^*) = \mathcal{O}(1)\omega(MST(G))$$

Therefore we have all the ingredients to prove .

\[Distributed Spanner\] \[thm:dis\]

It directly follows from Lemma \[lem:dis-rnd\], Lemma \[lem:dis-str\], Lemma \[lem:dis-deg\], and Proposition \[prp:dis-light\].

Low-intersection construction {#sec:euc}
=============================

The two dimensional Euclidean case of the unit ball graphs, also known as unit disk graphs, had gained a significant attention once it was introduced, due to its direct application in wireless ad-hoc networks. A huge amount of effort is still being made to improve the existing spanners in some aspects, or to introduce new constructions that possess good qualities, e.g. being fault tolerant, or having a low interference @mulzer2020compact [@wu2018topology; @chan2019approximate; @yu2017distributed].

In this section, we take the edge intersection as a simple representation of physical link-to-link interference, and we provide a distributed construction for a light-weight low-intersection bounded-degree spanner for unit disk graphs in the two dimensional Euclidean plane. To the best of our knowledge, this is the first distributed low-intersection construction with constant bounds on the degree and the the lightness.

We need to emphasize that after removing the edges of longer than 1 from the output of on a unit disk graph $G$, the remaining graph would be a $(1+\epsilon)$-spanner of $G$ and it also has constant bounds on its lightness, maximum degree, and average number of edge intersections per node. Equivalently, we can stop the algorithm before reaching the pairs with distance greater than 1 and the resulting spanner would be the same. We present this centralized algorithm in the following form and we use it as a part of our distributed algorithm.

\[ht\]

**Input.** A unit disk graph $G(V,E)$ in the two dimensional Euclidean plane.\
**Output.** A light-weight low-intersection bounded-degree $(1+\epsilon)$-spanner of $G$.

\[1\]Let $S$ be a graph with vertices $V$ and edges $E=\{\}$**break** Add edge $PQ$ to $E$S

\[Centralized Euclidean Spanner\] \[thm:euc-cent\]

The stretch-factor follows directly from the fact that every edge of the UDG can be approximated by a spanner path within a factor of $t$ (otherwise the edge would have been added to the spanner). And since the spanner is a sub-graph of the greedy spanner on the complete weighted graph on $V$, we can deduce that its lightness, its maximum degree, and its average number of edge intersections per node are bounded by the lightness, maximum degree, and the average number of edge intersections per node of the greedy spanner, respectively. And these are all bounded by constants according to @filtser2016greedy and @eppstein2020edge.

Now we focus on the distributed construction. Our distributed algorithm () is based on the algorithm we presented in , with a small change that we use the procedure as a sub-routine instead of . The pseudo-code is provided in .

\[ht\]

**Input.** A unit disk graph $G(V,E)$ in the two dimensional Euclidean plane.\
**Output.** A light-weight bounded-degree $(1+\epsilon)$-spanner of $G$.

\[1\]Find a maximal independent set $I$ of $G$ using @schneider2008logRun on the vertices of $G$Retrieve $\mathcal{N}^2(w)$, the 2-hop neighborhood information of $w$$\mathcal{S}_w \gets $ Send $e$ to $u$ and $v$Listen to incoming edges and store them

Similar to this algorithm runs in $\mathcal{O}(\log^* n)$ rounds of communications during which it builds a $(1+\epsilon)$-spanner of the unit disk graph $G$.

The spanner returned by has a stretch-factor of $1+\epsilon$, a weight of $\mathcal{O}(1)\omega(MST)$, and a maximum degree of $\mathcal{O}(1)$.\[lem:euc-dist-prop\]

The proof follows from Lemma \[lem:dis-str\], Proposition \[prp:dis-light\], and Lemma \[lem:dis-deg\] which all hold for this construction as well.

Now we prove the low-intersection property of our distributed construction.

The spanner returned by has at most a linear number of edge intersections.\[prp:euc-dist-int\]

We use the result of Eppstein and Khodabandeh @eppstein2020edge on the edge crossings of the greedy spanner, which states that an arbitrary edge $AB$ of the greedy spanner intersects with at most a constant number of longer edges. It is easy to see that the same statement is true when $AB$ is an arbitrary segment on the plane, and the assumption of $AB$ being an edge of the spanner is not necessary in the proof of the theorem. Therefore we may safely remove this assumption. The modified statement of the theorem for our case would be as follows,

\[Theorem 17 from @eppstein2020edge\] Given an arbitrary segment $\lVert AB\rVert \leq 1$ in the plane, the number of edges $e\in S$ that intersect $AB$ and $|e|\geq \lVert AB\rVert$ is bounded by a constant.\[lem:int-ES\]

See Theorem 17 from @eppstein2020edge.

We follow the same approach as in @eppstein2020edge and we bound the number of intersections of each edge of the spanner with the longer edges, which in turn proves the linear bound on the number of intersections.

Let $e=(u,v)$ be an edge of the final spanner and let $f=(u',v')\in S_w$ for some $w$ be another edge that intersects $e$. By the triangle inequality, at least one of $u'$ and $v'$ needs to be adjacent to $u$ in $G$. Thus $u\in\mathcal{N}^3(w)$, which means that $\lVert uw\rVert \leq 3$. So by the packing property there are at most $12^2=144$ different choices for $w$ that $u\in\mathcal{N}^3(w)$. But for every such $w$, according to Lemma \[lem:int-ES\] for the segment $AB=e$, there are at most a constant number of intersections between $e$ and the edges of length larger than $|e|$ in $S_w$. Since there are at most a constant number of choices for $w$ and for each choice there are at most a constant number of intersections between $e$ and the longer edges in $S_w$, we conclude that the number of intersections between $e$ and longer edges in the final spanner would be bounded by a constant, which indeed proves the proposition.

Thus the following theorem holds for our distributed spanner construction for the two dimensional Euclidean plane.

\[Distributed Euclidean Spanner\] \[thm:euc-dist\]

Follows directly from Lemma \[lem:euc-dist-prop\] and Proposition \[prp:euc-dist-int\].

Conclusion
==========

In this paper we resolved an open question from 2006 and we proved the existence of light-weight bounded-degree $(1+\epsilon)$-spanners for unit ball graphs in the spaces of bounded doubling dimension. Moreover, we provided a centralized construction and a distributed construction that finds a spanner with these properties. Our distributed construction runs in $\mathcal{O}(\log^* n)$ rounds, where $n$ is the number of vertices in the graph. If a maximal independent set of the unit ball graph is known beforehand, our algorithm runs in constant number of rounds.

In addition, we adjusted these algorithms for the case of unit disk graphs in the two dimensional Euclidean plane, and we presented the first centralized and distributed constructions for a light-weight bounded-degree $(1+\epsilon)$-spanner that also has a linear number of edge intersections in total. This can be useful for practical purposes if minimizing the number of edge intersections is a priority.

{'source': 'arXiv_out/2106'}