# Almost All Even Yao-Yao Graphs Are Spanners

Jian Li Wei Zhan
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

It is an open problem whether Yao-Yao graphs $\mathsf{YY}_{k}$ (also known as
sparse-Yao graphs) are all spanners when the integer parameter $k$ is large
enough. In this paper we show that, for any integer $k\geq 42$, the Yao-Yao
graph $\mathsf{YY}_{2k}$ is a $t_{k}$-spanner, with stretch factor
$t_{k}=6.03+O(k^{-1})$ when $k$ tends to infinity. Our result generalizes the
best known result which asserts that all $\mathsf{YY}_{6k}$ are spanners for
$k\geq 6$ [Bauer and Damian, SODA’13]. Our proof is also somewhat simpler.

##  1 Introduction

Let $\mathcal{P}$ be a set of points on the Euclidean plane $\mathbb{R}^{2}$.
A simple undirected graph $G=(V,E)$ with vertex set $V=\mathcal{P}$ is called
a geometric $t$-spanner, if for any pair of vertices $(u,v)$ there is a path
$uu_{1}\ldots u_{s}v$ in $G$ such that the total length of the path
$|uu_{1}|+|u_{1}u_{2}|+\ldots+|u_{s}v|$ is at most $t$ times the Euclidean
distance $|uv|$, where $t$ is a constant, called the stretch factor. The
concept of geometric spanners was first proposed in [7], and can be considered
as a special case of general graph spanners [21] if we consider the complete
graph with edge lengths defined by the Euclidean metric.

Yao graph was first introduced by Andrew Yao in his seminal work on high-
dimensional Euclidean minimum spanning trees [23]. Let
$C_{u}(\gamma_{1},\gamma_{2})$ be the cone with apex $u$ and consisting of the
rays with polar angles in $[\gamma_{1},\gamma_{2})$. Given a positive integer
parameter $k$, the construction of Yao graph $\mathsf{Y}_{k}$ is described in
the following process.

Initially $\mathsf{Y}_{k}$ is an empty graph.
---
For each point $u$:
| For each $j=0,\ldots,k-1$:
|  | Let $C=C_{u}(2j\pi/k,2(j+1)\pi/k)$;
|  | Select $v\in C\cap\mathcal{P}$ such that $|uv|$ is the shortest;
|  | Add edge $\overrightarrow{uv}$ into $\mathsf{Y}_{k}$.

In the above process, ties are broken in an arbitrary but consistent manner.
The above process is usually referred to as a “Yao step”. Note that the edges
$\overrightarrow{uv}$ we added are directed edges (the directions are useful
in the construction of Yao-Yao graphs).

Besides the usefulness in constructing minimum spanning trees, Yao graphs are
also sparse graphs with surprisingly nice spanning properties. It is known
that Yao graph $\mathsf{Y}_{k}$ has a stretch factor $(1-2\sin(\pi/k))^{-1}$
when $k\geq 6$ (see e.g., [18] and [5]). Later, the spanning properties of
$\mathsf{Y}_{4}$, $\mathsf{Y}_{6}$ and $\mathsf{Y}_{5}$ are proved in a series
of work [10, 11, 2]. Due to the spanning properties and the simplicity of the
construction, they have important applications in networking and wireless
communication; we refer to [20] and [16] for more details.

One may notice that a Yao graph may not have a bounded degree. This is a
serious drawback in certain wireless networking applications, since a wireless
node can only communicate with a bounded number of neighbors. The issue was
initially realized by Li et al. [18]. To address the issue, they proposed a
modified construction with two Yao steps: the first Yao step produces a Yao
graph $\mathsf{Y}_{k}$, and the second step, called the “reverse Yao step”,
eliminates a subset of edges of $\mathsf{Y}_{k}$ to ensure the maximum degree
is bounded. The reverse Yao step can be described by the following procedure:

Initially $\mathsf{YY}_{k}$ is an empty graph.
---
For each point $u$:
| For each $j=0,\ldots,k-1$:
|  |  $C=C_{u}(2j\pi/k,2(j+1)\pi/k)$;
|  | Select $v\in C\cap\mathcal{P}$, $\overrightarrow{vu}\in\mathsf{Y}_{k}$ such that $|uv|$ is the shortest;
|  | Add edge $\overrightarrow{vu}$ into $\mathsf{YY}_{k}$.

The resulting graph, $\mathsf{YY}_{k}$, is named as “Yao-Yao graph” or
“Sparse-Yao graph” in the literature. The node degrees in $\mathsf{YY}_{k}$
are clearly upper-bounded by $2k$. It has long been conjectured that
$\mathsf{YY}_{k}$ are also geometric spanners when $k$ is larger than some
constant threshold [18, 16, 3]:

######  Conjecture 1.

There exists a constant $k_{0}$ such that for any integer $k>k_{0}$,
$\mathsf{YY}_{k}$ is a geometric spanner.

In sharp contrast to Yao graphs, our knowledge about the spanning properties
of Yao-Yao graphs is still quite limited. Li et al. [18] proved that
$\mathsf{YY}_{k}$ is connected for $k>6$, and provided extensive experimental
evidence suggesting $\mathsf{YY}_{k}$ are indeed spanners for larger $k$. Jia
et al. [14] and Damian [9] showed that $\mathsf{YY}_{k}$ is spanner in certain
special cases (the underlying point set satisfies certain restrictions). It is
also known that for small constant $k$’s, none of $\mathsf{YY}_{k}$ with
$2\leq k\leq 6$ admits a constant stretch factor [2, 10, 13]. Recently, a
substantial progress was made by Bauer and Damian [3], who showed that
$\mathsf{YY}_{6k}$ are spanners with stretch factor $11.76$ for all integer
$k\geq 6$ and the factor drops to $4.75$ when $k\geq 8$. In fact, a closer
examination of the proofs in their paper actually implies an asymptotic
stretch factor of $2+O(k^{-1})$. None of $\mathsf{YY}_{k}$ with other $k$
values have been proved or disproved to be spanners. We note here that some of
the aforementioned work [18, 9] focused on UDGs (unit disk graphs). But their
arguments can be easily translated to general planar point sets as well.
111Suppose a spanning property holds for any UDG. For a general set of points,
we first scale it so that its diameter is less than 1. We can see that the UDG
defined over the scaled set is a complete graph. So the spanning property also
holds for the set of points.

In this paper, we improve the current knowledge of Yao-Yao graphs and make a
step towards the resolution of Conjecture 1, by showing that almost all Yao-
Yao graphs with even $k$ are geometric spanners for $k$ large enough.
Formally, our results is as follows:

######  Theorem 2.

For any $k\geq 42$, $\mathsf{YY}_{2k}$ is a $t_{k}$-spanner, where
$t_{k}=6.03+O(k^{-1})$.

#### Our Technique

Our proof contains two major steps.

  1. 1.

(Section 3) We first introduce two classes of intermediate graphs, called
overlapping Yao graphs (denoted as $\mathsf{OY}_{k}$) and trapezoidal Yao
graphs (denoted as $\mathsf{TY}_{k}$). The construction of overlapping Yao
graphs is similar to that of Yao graphs, except that the cones incident on a
vertex overlap with each other. We can easily show that $\mathsf{OY}_{k}$ is a
geometric spanner. The definition of trapezoidal Yao graphs is also similar to
Yao graphs, but takes advantage of a shape called curved trapezoid (defined in
Section 2). We can show that $\mathsf{OY}_{k}$ is a subgraph of
$\mathsf{TY}_{k}$, implying $\mathsf{TY}_{k}$ is a geometric spanner as well.

  2. 2.

(Section 4) In the second step, we show that $\mathsf{YY}_{2k}$ spans
$\mathsf{TY}_{2k}$ (i.e., for any $u,v\in\mathcal{P}$, the shortest $u$-$v$
path in $\mathsf{YY}_{2k}$ is at most a constant times longer than the
shortest $u$-$v$ path in $\mathsf{TY}_{2k}$).

Our proof makes crucial use of the properties of curved trapezoids. Roughly
speaking, curved trapezoids are more flexible than triangles which were used
in [3]), which is the main reason for the improvement from $\mathsf{YY}_{6k}$
to more general $\mathsf{YY}_{2k}$.

#### Related Works

Replacing the Euclidean distance $|\cdot|$ by a power $|\cdot|^{\kappa}$ with
a constant $\kappa\geq 2$ leads to the definition of power spanners. Since the
power of length models the energy consumed in wireless transmissions, power
spanners have important implications in wireless networking applications. In
this setting, Yao-Yao graphs $\mathsf{YY}_{k}$ have been proved to be power
spanners for any $\kappa\geq 2$ when $k>6$ [14, 22]. It is clear that when a
graph is a geometric spanner, it must also be a power spanner (See [17, Lemma
1]), however the reverse does not hold.

We also note that neither Yao graphs nor Yao-Yao graphs can be guaranteed to
be planar graphs [22, 15], whereas Delaunay triangulation provides another
type of spanner which is planar but without bounded degree [12, 4]. In order
to facilitate network design in certain applications, some previous work [6,
19] made use of both Yao graphs and Delaunay graphs to produce degree-bounded
and planar geometric spanners.

The paper is organized as follows. We introduce some standard notations and
useful tools, including the shape of curved trapezoid, in Section 2. We
introduce overlapping Yao graphs, trapezoidal Yao graphs, and prove their
spanning properties in Section 3. We prove our main result in Section 4.
Finally, we conclude with some future work in Section 5.

##  2 Preliminaries

$\mathcal{P}$ is the underlying set of points in $\mathbb{R}^{2}$. $D(a,\rho)$
denotes an open disk centered at point $a$ with radius $\rho$. The boundary
and closure of a region $R$ are denoted by $\partial R$ and $\overline{R}$,
respectively. Let $S(a,\rho)=\partial D(a,\rho)$ be the circle centered at $a$
with radius $\rho$. The length of shortest $u$-$v$ path in a graph $G$ is
denoted by $d_{G}(u,v)$.

On $\mathbb{R}^{2}$, a point $u$ with coordinates $(x,y)$ is denoted by
$u(x,y)$. Let $o(0,0)$ be the origin of $\mathbb{R}^{2}$. The positive
direction of $x$-axis is fixed as the polar axis throughout the construction
and analysis. For a point $a\in\mathbb{R}^{2}$, we use $x_{a}$ to denote its
$x$-coordinate and $y_{a}$ its $y$-coordinate. We use $\varphi(uv)$ to
represent the polar angle of vector $\overrightarrow{uv}$. The angle
computations are all under the modulo of $2\pi$, and angle subtraction is
regarded as the counterclockwise difference. A cone between polar angles
$\gamma_{1}<\gamma_{2}$ with apex at the origin is denoted as
$C(\gamma_{1},\gamma_{2})=\\{u\mid\varphi(ou)\in[\gamma_{1},\gamma_{2})\\}$.

It is also necessary to introduce some notations of standard affine
transformations on a geometric object $\mathcal{O}$ in the plane:

  * -

(Dilation) If $\mathcal{O}$ is uniformly scaled by factor $\lambda$ with the
origin as the center, the result is denoted by $\lambda\mathcal{O}=\\{\lambda
z\mid z\in\mathcal{O}\\}$.

  * -

(Translation) If $\mathcal{O}$ is translated so that the original point goes
to point $u$, the result is denoted by $u+\mathcal{O}=\\{u+z\mid
z\in\mathcal{O}\\}$.

  * -

(Rotation) If $\mathcal{O}$ rotated an angle $\gamma$ counterclockwise with
respect to the origin, the result is denoted by
${\mathcal{O}}^{\circlearrowleft\gamma}$.

  * -

(Reflection) If $\mathcal{O}$ is reflected through the $x$-axis, the result is
denoted by $\mathcal{O}^{-}$.

By the above notations, we can denote the cone with apex $u$ by
$u+C(\gamma_{1},\gamma_{2})$ (abbreviated as $C_{u}(\gamma_{1},\gamma_{2})$).

Figure 1: Left: Affine transformations. Right: Proof for Lemma 3.

### Geometric Inequalities

In order to attain a constant stretch factor for Yao graphs and their
variants, one often needs to bound a certain geometric ratio. Here we present
a simple yet general lemma for this purpose. Let the open strip on the segment
$uv$ be the collection of points

######  Lemma 3.

Suppose $\tau\geq 1$ is a constant. Let $w$ be a point with $\angle wuv,\angle
wvu\in[0,\pi/2)$ (see Figure 1). When $\tau|vw|<|uv|$, the following
statements about the ratio $|uw|/(|uv|-\tau|vw|)$ hold:

  1. 1.

If $w$ is restricted within a compact segment of an arc centered at $u$, the
ratio is maximized when $|vw|$ is the largest;

  2. 2.

If $w$ is restricted within a compact segment of a ray from $v$, the ratio is
maximized when $|vw|$ is the largest;

  3. 3.

If $w$ is restricted within a compact segment of a ray originated from $u$,
the maximum ratio is achieved when $w$ makes $|uw|$ the largest or smallest;

###### Proof.

The first statement is straightforward since both $|uv|$ and $|uw|$ are fixed.
Now, we show the last two properties. Let $\alpha=\angle wuv$ and
$\beta=\angle wvu$. By the law of sines and the fact that
$\sin(\alpha+\beta)=\sin\alpha\cos\beta+\cos\alpha\sin\beta$, we can see that

$\dfrac{|uw|}{|uv|-\tau|vw|}=\frac{\sin\beta}{\sin(\alpha+\beta)-\tau\sin(\alpha)}=\frac{1}{\cos\alpha-\sin\alpha\cdot(\tau-\cos\beta)/\sin\beta}.$
(1)

One can see the ratio is maximized when $\alpha$ is maximized, which implies
the second statement. Moreover, $(\tau-\cos\beta)/\sin\beta$ is a convex
function of $\beta$ for $\beta\in(0,\pi/2)$. Hence, it is maximized when
$\beta$ is maximized or minimized, which implies the last statement. ∎

Due to Lemma 3, to compute an upper bound for $|uw|/(|uv|-|vw|)$ in a region,
it suffices to consider a small number of extreme positions. In particular,
the following corollary is an immediately consequence, which is an improvement
of a classical result mentioned in [8]:

######  Corollary 4.

$R=\overline{D(u,|uv|)\cap C_{u}(\gamma_{1},\gamma_{2})}$ is a sector with
apex $u$ and with $v$ on its arc. Suppose
$\alpha=\max\\{\varphi(uv)-\gamma_{1},\gamma_{2}-\varphi(uv)\\}<\pi/3$. Then,
for all $w\in R\setminus\\{u\\}$, it holds that

$\dfrac{|uw|}{|uv|-|vw|}\leq\left(1-2\sin\frac{\alpha}{2}\right)^{-1}.$

###### Proof.

Take $\tau=1$ in Lemma 3. By considering the rays from $u$ and the arcs
centered at $u$, and applying the first and third cases in Lemma 3, we can see
that the ratio can only be maximized when $w$ is at the two corners of the
sector with $\beta=(\pi-\alpha)/2$, or when $w$ approaches $u$ with $\beta=0$.
The two upper bounds in equality 1 in these cases are
$\left(1-2\sin(\alpha/2)\right)^{-1}$ and $(\cos\alpha)^{-1}$, and the former
one is larger. ∎

### Curved Trapezoid $T_{\theta}$

To construct the trapezoidal Yao Graphs $\mathsf{TY}_{k}$, we need to define
an open shape, called curved trapezoid, as follows.

######  Definition 1 (Curved Trapezoid $T_{\theta}$).

Fix two points $o(0,0)$ and $p(1,0)$. Given $\theta\in[\pi/4,\pi/3)$, we
define the curved trapezoid $T_{\theta}$ as:

$T_{\theta}=\\{u(x,y)\mid 0<x<1,0<y<\sin\theta,|ou|<1,|pu|<1\\}.$

Intuitively, it is the convex hull of two sectors with apices at $o$ and $p$
respectively. We regard $T_{\theta}$ as a shape attached to the origin $o$,
and the closed arc not incident on $o$ is called the critical arc. See Figure
2 for an example.

Figure 2: Left: The curved trapezoid. The critical arc is shown in bold.
Right: An illustration of Lemma 5 with its proof.

We list some useful properties of $T_{\theta}$ here. It is straightforward to
show that $T_{\theta}$ is symmetric with respect to the vertical line
$x=\frac{1}{2}$. For any $u\in T_{\theta}$ it holds that
$0<\varphi(ou)<\pi/2$. If $u$ is on the critical arc, it holds that
$0<\varphi(ou)<\theta$. The following crucial lemma, illustrated in Figure 2,
is also an immediate consequence from the definition.

######  Lemma 5.

Denote $\mathbb{R}^{2}_{-}$ as the lower half-plane $\\{(x,y)\mid y\leq 0\\}$.
Consider any two points $u,v\in\mathbb{R}^{2}_{-}$ satisfying $0<x_{u}<1$,
$|\varphi(uv)-\pi|<\dfrac{1}{6}\pi$, and $|ou|,|pv|\in[|uv|,1)$. We construct
a similar shape
$T_{\theta}^{\prime}:=u+|uv|{(T_{\theta}^{-})}^{\circlearrowleft\varphi(uv)}$.
We have that $T_{\theta}^{\prime}-T_{\theta}$ is completely contained in lower
half plane $\mathbb{R}^{2}_{-}$.

###### Proof.

We first consider the extreme case when $\theta=\pi/3$. Since
$u,v\in\mathbb{R}^{2}_{-}$, if the two arcs of $T_{\theta}^{\prime}$ do not
intersect with the line $y=0$, then $T_{\theta}$ is fully contained in
$\mathbb{R}^{2}_{-}$ and the proof is done.

Now suppose the two intersections are $a,b$, illustrated in the RHS of Figure
2. Notice that $|ua|=|uv|\leq|ou|$ and $|vb|=|uv|\leq|pv|$. Combining with the
condition that $0<x_{u}<1$, we can see that both $a$ and $b$ lie in the
segment $op$. For any point $w\in T_{\theta}^{\prime}-\mathbb{R}^{2}_{-}$, it
suffices to prove $|ow|,|pw|<1$ so that $w$ is in $T_{\theta}$. This is done
by examining the perpendicular bisector of $aw$ and $bw$: since $|ua|>|uw|$,
$u$ is in the upper half-plane of the bisector of $aw$, and so is $p$. Thus
$|pw|<|pa|\leq|op|=1$. The same arguments hold for $|ow|<1$.

The above shows that $T_{\theta}^{\prime}-T_{\theta}\subset\mathbb{R}^{2}_{-}$
when $\theta=\pi/3$, and if $\theta$ is smaller, we only need to show that the
distance $d(w,op)$ from $w$ to line $y=0$ is less than $\sin\theta$. This is
done by the observation that $d(w,ab)\leq d(w,uv)$ in $T_{\theta}^{\prime}$,
and $d(w,uv)<|uv|\sin\theta<\sin\theta$. This completes the proof for Lemma 5.
∎

##  3 Overlapping Yao Graphs and Trapezoidal Yao Graphs

In this section we consider two variants of Yao graphs, overlapping Yao graphs
and trapezoidal Yao graphs.

######  Definition 2 (Overlapping Yao Graph $\mathsf{OY}_{k}$).

Let $\gamma=\left\lceil\dfrac{k}{4}\right\rceil\dfrac{2\pi}{k}$. For every
$u\in\mathcal{P}$ and $j=0,\ldots,k-1$, select shortest $\overrightarrow{uv}$
with $v\in C_{u}(2j\pi/k,2j\pi/k+\gamma)$. The chosen edges form the
overlapping Yao graph $\mathsf{OY}_{k}(\mathcal{P})$.

The angle $\gamma$ in the definition is actually the smallest multiple of
$2\pi/k$ which is no less than $\pi/2$. We note here that the term
“overlapping” comes from the fact that the cones with the same apex overlap
with each other, while in the original Yao graphs they are disjoint. First we
claim that $\mathsf{OY}_{k}$ is a spanner when $k$ is large.

######  Lemma 6.

If $k>24$, then $\mathsf{OY}_{k}$ is a $\tau_{k}$-spanner where
$\tau_{k}=\left(1-2\sin\big{(}\dfrac{\pi}{k}+\dfrac{\pi}{8}\big{)}\right)^{-1}$.

Figure 3: Illustration of the proof of Lemma 6. The outer cone is
$C_{u}(\gamma_{1},\gamma_{2})$ where $\gamma_{1}=2j\pi/k$ and
$\gamma_{2}=2j\pi/k+\gamma$ The cone defined by two dashed lines is
$C_{u}\left(2j\pi/k+\pi/4,2(j+1)\pi/k+\pi/4\right)$.

###### Proof.

We prove $d_{\mathsf{OY}}(u,v)\leq\tau_{k}|uv|$ by induction on the length
$|uv|$ for $u,v\in\mathcal{P}$. Notice that it is always possible to find $j$
so that $v\in C_{u}\left(2j\pi/k+\pi/4,2(j+1)\pi/k+\pi/4\right)$. See Figure 3
for an illustration. This cone is contained in $C_{u}(\gamma_{1},\gamma_{2})$,
where $\gamma_{1}=2j\pi/k$ and $\gamma_{2}=2j\pi/k+\gamma$, since $k>24$ and
thus $\gamma\geq\pi/2$. If $\overrightarrow{uv}$ is the shortest in
$C_{u}(\gamma_{1},\gamma_{2})$, then $\overrightarrow{uv}\in\mathsf{OY}_{k}$
and we are done with the proof.

Now, suppose that in the construction of construction of $\mathsf{OY}_{k}$, we
choose $\overrightarrow{uw}$ for $C_{u}(\gamma_{1},\gamma_{2})$ with $w\neq
v$. Since $k>24$, one shall see that

$\displaystyle\alpha$ $\displaystyle:=$
$\displaystyle\max\\{\varphi(uv)-\gamma_{1},\gamma_{2}-\varphi(uv)\\}$
$\displaystyle\leq$
$\displaystyle\max\\{2\pi/k+\pi/4,\gamma-\pi/4\\}=2\pi/k+\pi/4<\pi/3.$

Hence, we can apply Corollary 4 on the sector $R=\overline{D(u,|uv|)\cap
C_{u}(\gamma_{1},\gamma_{2})}$, which claims

$\dfrac{|uw|}{|uv|-|vw|}\leq\tau_{k}=\left(1-2\sin\frac{\alpha}{2}\right)^{-1}.$

Since $\alpha<\pi/3$, we have $|vw|<|uv|$. By the induction hypothesis, we can
see that

$d_{\mathsf{OY}}(u,v)\leq|uw|+d_{\mathsf{OY}}(v,w)\leq|uw|+\tau_{k}|vw|\leq\tau_{k}(|uv|-|vw|)+\tau_{k}|vw|=\tau_{k}|uv|,$

which completes the proof. ∎

We also note that Barba et al. proposed the so-called continuous Yao graphs in
[1], which play a similar role as $\mathsf{OY}_{k}$. By adapting their method,
it might be possible to prove a slightly smaller stretch factor for
$\mathsf{OY}_{k}$. However the constant is not our primary goal in this paper,
and we leave it to the future work.

Now we define the trapezoidal Yao graphs based on the curved trapezoid
$T_{\theta}$ (Definition 1).

######  Definition 3 (Trapezoidal Yao Graph $\mathsf{TY}_{k}$).

Let $\theta=\left\lceil\dfrac{k}{8}\right\rceil\dfrac{2\pi}{k}$. For every
$u\in\mathcal{P}$ and $j=0,\ldots,k-1$, define two curved trapezoids

$\Gamma_{j1}={(T_{\theta})}^{\circlearrowleft
2j\pi/k}\qquad\text{and}\qquad\Gamma_{j2}={(T_{\theta}^{-})}^{\circlearrowleft
2j\pi/k}.$

Note that their bottom sides lie on the ray of angle $2j\pi/k$. For each
$i=1,2$, we do the following: We grow a curved trapezoid
$u+\lambda\Gamma_{ji}$ by gradually increasing $\lambda$ (initially 0) until
its boundary hits some point $v$. If the critical arc hits $v$, we select
$\overrightarrow{uv}$. Otherwise, we select nothing. All the selected edges
form the graph $\mathsf{TY}_{k}(\mathcal{P})$.

Figure 4: Illustration for Lemma 7: Two curved trapezoids cover a sector.

######  Lemma 7.

For any integer $k>24$, $\mathsf{TY}_{k}$ is a $\tau_{k}$-spanner where
$\tau_{k}=\left(1-2\sin\big{(}\dfrac{\pi}{k}+\dfrac{\pi}{8}\big{)}\right)^{-1}$.

###### Proof.

Note that in Definition 1, we require that $\theta\in[\pi/4,\pi/3)$. When
$k>24$, we can see that

$\dfrac{\pi}{4}\leq\theta=\left\lceil\dfrac{k}{8}\right\rceil\dfrac{2\pi}{k}\leq\dfrac{k+7}{k}\cdot\dfrac{\pi}{4}<\dfrac{\pi}{3}.$

Hence, the value $\theta$ in Definition 3 satisfies the requirement of
$\theta$ in Definition 1.

We show that the overlapping Yao graph $\mathsf{OY}_{k}$ is actually a
subgraph of $\mathsf{TY}_{k}$, from which the lemma is an immediate
consequence. Given any $j$ and one cone $C_{u}(2j\pi/k,2j\pi/k+\gamma)$, we
choose two copies of $T_{\theta}$:
$\Gamma_{1}={(T_{\theta})}^{\circlearrowleft 2j\pi/k}$, and
$\Gamma_{2}={(T_{\theta}^{-})}^{\circlearrowleft 2j\pi/k+\gamma}$. See Figure
4. Since $2\theta\geq\gamma\geq\pi/2$, it is clear that $\Gamma_{1}$ and
$\Gamma_{2}$ exactly cover the interior of sector $D(o,1)\cap
C_{o}(2j\pi/k,2j\pi/k+\gamma)$. Now, for any edge
$\overrightarrow{uv}\in\mathsf{OY}_{k}$ selected within this cone, both
$u+|uv|\Gamma_{1}$ and $u+|uv|\Gamma_{2}$ must have empty interior ($|uv|$ is
the shortest within the cone). Therefore, if $\varphi(uv)-2j\pi/k\leq\theta$,
it should be selected into $\mathsf{TY}_{k}$ with respect to $\Gamma_{1}$.
Otherwise it should be selected with respect to $\Gamma_{2}$. This implies
that $\mathsf{OY}_{k}$ is a subgraph of $\mathsf{TY}_{k}$, and by Lemma 6,
$\mathsf{TY}_{k}$ is a $\tau_{k}$-spanner as well. ∎

##  4 Yao-Yao Graphs $\mathsf{YY}_{2k}$ are Spanners

In this section, we prove our main result that $\mathsf{YY}_{2k}$ has a
constant stretch factor for large $k$, by show that $\mathsf{YY}_{2k}$ spans
$\mathsf{TY}_{2k}$.

To begin with, we prove an important property of $\mathsf{TY}_{2k}$, which
will be useful later. The property can be seen as an analogue of the property
of $\Theta_{6}$ shown in [3, Lemma 2]. One of the reasons we can improve
$\mathsf{YY}_{6k}$ to more general $\mathsf{YY}_{2k}$ is that we can take
advantage of the curved trapezoid rather than the regular triangle. We state
this property by assuming, that without loss of generality, a curved trapezoid
$T_{\theta}$ is placed at its normal position, i.e., $T_{\theta}$ lies in the
first quadrant with two vertices $o(0,0)$ and $p(1,0)$. From now on, we work
with trapezoidal Yao graphs $\mathsf{TY}_{2k}$. Hence, the associated
parameter $\theta$ (see Definition 3) is
$\theta=\left\lceil\dfrac{2k}{8}\right\rceil\dfrac{2\pi}{2k}=\left\lceil\dfrac{k}{4}\right\rceil\dfrac{\pi}{k}$.

######  Lemma 8.

Suppose $o\in\mathcal{P}$ and $T_{\theta}$ has an empty interior. If there is
a point $a\in\mathcal{P}$ such that $0<x_{a}<1$, $y_{a}\leq 0$ and
$0<\varphi(ap)<\pi/6$, then

$d_{\mathsf{TY}}(oa)\leq x_{a}+(2\tau_{2k}+1)|y_{a}|$

where $\tau_{k}$ is as defined in Lemma 7, and there is a path in
$\mathsf{TY}_{2k}$ from $a$ to $o$ where each edge is shorter than $|oa|$.

###### Proof.

Note that simply applying Lemma 7 is insufficient to achieve the guarantee.
Instead, we present an iterative algorithm for finding a path from $a$ to $o$.
The path found by the iterative algorithm is not necessarily a shortest path
from $a$ to $o$. Nevertheless, we can bound its length as in the lemma.

Figure 5: Illustration of three cases in the proof of Lemma 8.

Let $u$ be the current point in $\mathcal{P}$; Initially $u$ is set to be $a$.
---
While $u\neq o$ and $\varphi(ou)>-\dfrac{\pi}{6}$ do
| Let $\psi=\min\\{j\pi/k\mid j\pi/k>\varphi(uo),j=0,1,\ldots,2k-1\\}$;
| Grow a curved trapezoid $u+\lambda{(T_{\theta}^{-})}^{\circlearrowleft\psi}$
until its boundary hits some point $v$.
| If $v\in C_{u}(\psi-\dfrac{\pi}{2},\psi-\theta)$:
|  | (i) $\mathsf{TY}_{2k}$ must contain the edge $\overrightarrow{uv}$. We add $\overrightarrow{uv}$ to our path;
| Otherwise:
|  | (ii) Add the path from $u$ to $v$ in $\mathsf{OY}_{2k}$ constructed in Lemma 6;
| Set the current point $u$ to be $v$ and proceed to the next iteration.
If now $u=o$, the path is already found;
(iii) Otherwise take the path from $u$ to $o$ in $\mathsf{OY}_{2k}$
constructed in Lemma 6.

See Figure 5 for an illustration of the three cases (i),(ii) and (iii). Let
$l(u)$ be the length of the path from $u$ to $o$ generated by the algorithm
above. To analyze its behaviour, we define a potential function

$\Phi(u)=x_{u}+(2\tau_{2k}+1)|y_{u}|-l(u).$

We claim that the potential function never increases as the algorithm proceeds
and is eventually $0$. The potential only changes in the three labeled steps
(i),(ii) and (iii). When executing step (i) and (ii), it is clear that
$\varphi(uo)\in\left(\dfrac{5}{6}\pi,\pi\right]$,
$\varphi(up)\in\left[0,\dfrac{1}{6}\pi\right)$. Therefore $\psi$ also falls in
the range $\left(\dfrac{5}{6}\pi,\pi\right]$. Moreover, $v$ must be contained
in $\mathbb{R}^{2}_{-}$ due to Lemma 5, that is, $y_{v}\leq 0$.

  * -

In step (i), $v$ is simply the nearest neighbor in the cone
$C_{u}(\psi-\theta,\psi)$. Since $\varphi(up)<\pi/6$, we know $|uv|<|vp|$.
Since $\psi-\theta>\pi/2$ and $\psi\leq\pi$, we can see that $x_{v}\leq x_{u}$
and $|y_{v}|<|y_{u}|$. Hence the change in potential is

$\displaystyle\Delta\Phi=\Phi(v)-\Phi(u)$
$\displaystyle=|uv|-(x_{u}-x_{v})-(2\tau_{2k}+1)(|y_{u}|-|y_{v}|)$
$\displaystyle\leq|uv|-(x_{u}-x_{v})-(|y_{u}|-|y_{v}|)\leq 0.$

  * -

In step (ii), since $\varphi(uv)\in[\psi-\dfrac{\pi}{2},\psi-\theta)$, we know
$|\varphi(uv)-\pi/2|$ is at most $\pi/4$, so $|y_{v}|<|y_{u}|$ and
$|x_{v}-x_{u}|<|y_{u}|-|y_{v}|$. That further implies
$|uv|<2(|y_{u}|-|y_{v}|)$, and thus
$d_{\mathsf{TY}}(uv)\leq\tau_{2k}|uv|<2\tau_{2k}(|y_{u}|-|y_{v}|)$. Therefore
the change in potential is

$\displaystyle\Delta\Phi=\Phi(v)-\Phi(u)$
$\displaystyle=d_{\mathsf{TY}}(uv)-(x_{u}-x_{v})-(2\tau_{2k}+1)(|y_{u}|-|y_{v}|)$
$\displaystyle=(d_{\mathsf{TY}}(uv)-2\tau_{2k}(|y_{u}|-|y_{v}|))+(x_{v}-x_{u}-(|y_{u}|-|y_{v}|))\leq
0.$

  * -

In step (iii), suppose the node arrived before $u$ is $u^{\prime}$, with
$\varphi(u^{\prime}o)>\dfrac{5}{6}\pi$. Since $\overrightarrow{u^{\prime}u}$
is chosen, it must be the case that $|u^{\prime}u|\leq|u^{\prime}o|$. It is
immediate that $\varphi(uo)\in\left(\dfrac{\pi}{3},\dfrac{5}{6}\pi\right]$,
and thus $|uo|\leq 2|y_{u}|$, $-x_{u}\leq|y_{u}|$. Therefore, we have that

$\Delta\Phi=\Phi(o)-\Phi(u)=(d_{\mathsf{TY}}(uo)-2\tau_{2k}|y_{u}|)+(-x_{u}-|y_{u}|)\leq
0.$

Now that $\Phi(o)=0$, and the above arguments show that the potential cannot
increase during the path from $u$ to $o$, we can conclude that $\Phi(a)\geq
0$. That is, $l(a)\leq x_{a}+(2\tau_{2k}+1)|y_{a}|$.

Also notice that in steps (i) and (ii), it is ensured that $|uv|<|ou|$ and
$|ov|<|ou|$ since $v$ is contained in the curved trapezoid. On the other hand,
the paths from $\mathsf{OY}_{2k}$ in steps (ii) and (iii), which are
constructed according to Lemma 6, contains only edges shorter than the direct
distance. Thus the edges we selected are all shorter than $|oa|$. ∎

######  Lemma 9.

On a Yao-Yao graph $\mathsf{YY}_{2k}(\mathcal{P})$ with $k\geq 42$, if
$\overrightarrow{uv}\in\mathsf{TY}_{2k}$, then
$d_{\mathsf{YY}}(uv)\leq\tau_{k}^{\prime}|uv|$, where
$\tau_{k}^{\prime}=\sqrt{2}+O(k^{-1})$ is a constant depending only on $k$.

###### Proof.

Let $\tau_{k}^{\prime}\geq 1$ be a constant to be fixed later. Our proof is by
induction on the length $|uv|$. The base case is simple: the shortest edge is
in both $\mathsf{TY}_{2k}$ and $\mathsf{YY}_{2k}$. Now, consider an edge
$\overrightarrow{uv}\in\mathsf{TY}_{2k}$. Without loss of generality, we
assume that $|uv|=1$. We further assume that $T_{\theta}$, which generates
$\overrightarrow{uv}$ in $\mathsf{TY}_{2k}$, in its normalized position, i.e.,
$u$ is $o(0,0)$ and another vertex is $p(1,0)$. See Figure 6. Noticing that
$\theta$ is a multiple of $\pi/k$, we can see that $v$ must be the nearest
neighbor of $u$ in its corresponding cone of $\mathsf{YY}_{2k}$.

If $\overrightarrow{uv}\in\mathsf{YY}_{2k}$, then $d_{\mathsf{YY}}(uv)=|uv|$
and we are done with the proof. Otherwise, there must be another edge
$\overrightarrow{wv}\in\mathsf{YY}_{2k}$ where $u$ and $w$ are in the same
$v$-apex cone, and $|vw|\leq|uv|$ (this is due to the construction of Yao-Yao
graph). It follows that $|uw|<|uv|$ since $k\geq 42$.

Now, we prove by induction that
$d_{\mathsf{YY}}(uv)\leq\tau_{k}^{\prime}|uv|$. Now noticing that $T_{\theta}$
has an empty interior, there are only two cases for $w$ we need to consider.
See Figure 6 for an example.

  1. 1.

$y_{w}>0$: See the left part of Figure 6. By Lemma 3, we can see that within
all possible positions of $w$, $|vw|/(|uv|-\tau_{2k}|uw|)$ can only be
maximized when $|vw|=|uv|$ or when $w$ is on the left boundary of
$T_{\theta}$. Since when $k\geq 42$, it holds
$2\tau_{2k}\sin\frac{\pi}{2k}<1$, therefore

$\dfrac{|vw|}{|uv|-\tau_{2k}|uw|}\leq\dfrac{1}{1-2\tau_{2k}\sin\frac{\pi}{2k}}.$

Hence, if $\tau_{k}^{\prime}\geq 1/(1-2\tau_{2k}\sin\frac{\pi}{2k})$, we have
that $|vw|\leq\tau_{k}^{\prime}(|uv|-\tau_{2k}|uw|).$ Consider the shortest
path from $u$ to $w$ in $\mathsf{TY}_{2k}$. Notice that
$d_{\mathsf{TY}}(uw)\leq\tau_{2k}|uw|<|uv|$. Applying the induction hypothesis
to every edge of the shortest path, we can see
$d_{\mathsf{YY}}(uw)\leq\tau_{k}^{\prime}d_{\mathsf{TY}}(uw)$. Combining the
above inequalities, we can finally obtain that

$d_{\mathsf{YY}}(uv)\leq
d_{\mathsf{YY}}(uw)+|vw|\leq\tau_{k}^{\prime}(d_{\mathsf{TY}}(uw)+|uv|-\tau_{2k}|uw|)\leq\tau_{k}^{\prime}|uv|.$

  2. 2.

$y_{w}\leq 0$: See the middle and right parts of Figure 6. Consider the two
cases of angle $\varphi(uv)$:

     * •

If $0\leq\varphi(uv)\leq\pi/k$, then $\varphi(wp)\leq\varphi(wv)\leq\pi/k$;

     * •

If $\pi/k<\varphi(uv)\leq\theta$, then $\angle
upv\leq\frac{(k-1)\pi}{2k}\leq\angle uwv$. Thus $p$ is outside the
circumcircle of $\triangle uvw$, and $\varphi(wp)=\angle upw\leq\angle
uvw\leq\pi/k$.

Therefore in both cases, we have $0<x_{w}<x_{p}$ and
$0\leq\varphi(wp)\leq\pi/k$. We notice the following two inequalities:

$\displaystyle|y_{w}|\leq(x_{p}-x_{w})\tan\varphi(wp)\leq(|uv|-x_{w})\tan\frac{\pi}{k},$
$\displaystyle|vw|\leq(x_{v}-x_{w})\sec\varphi(wv)\leq(|uv|-x_{w})\sec\left(\theta+\frac{\pi}{k}\right).$

Consider the path from $w$ to $u$ as we constructed in Lemma 8 ($w$ and $u$
correspond to $a$ and $o$ in the lemma, respectively). Since all edges in the
constructed path are shorter than $|wu|$ (thus shorter than $|uv|$ as well),
we can apply the induction hypothesis to get
$d_{\mathsf{YY}}(uw)\leq\tau_{k}^{\prime}d_{\mathsf{TY}}(uw)$. Applying Lemma
8, we have

$\displaystyle d_{\mathsf{YY}}(uv)$ $\displaystyle\leq
d_{\mathsf{YY}}(uw)+|vw|\leq\tau_{k}^{\prime}d_{\mathsf{TY}}(uw)+|vw|$
$\displaystyle\leq\tau_{k}^{\prime}(x_{w}+(2\tau_{2k}+1)|y_{w}|)+|vw|$
$\displaystyle\leq\tau_{k}^{\prime}x_{w}+\left(\tau_{k}^{\prime}(2\tau_{2k}+1)\tan\frac{\pi}{k}+\sec\left(\theta+\frac{\pi}{k}\right)\right)(|uv|-x_{w}).$

Suppose we choose $\tau_{k}^{\prime}$ such that
$\tau_{k}^{\prime}(2\tau_{2k}+1)\tan\frac{\pi}{k}+\sec(\theta+\frac{\pi}{k})\leq\tau_{k}^{\prime},$
(which is equivalent to
$\tau^{\prime}\geq((1-(2\tau_{2k}+1)\tan\frac{\pi}{k})\cos(\theta+\frac{\pi}{k}))^{-1}$
). Note that the above holds also because $(2\tau_{2k}+1)\tan\frac{\pi}{k}<1$
when $k\geq 42$. Finally, we can conclude that

$d_{\mathsf{YY}}(uv)\leq\tau^{\prime}_{k}|uv|.$

Figure 6: Proof for Lemma 9. Left: $w$ is in the upper half-plane; Middle: $w$
is in the lower half-plane and $\varphi(uv)\leq\pi/k$; Right: $w$ is in the
lower half-plane and $\varphi(uv)>\pi/k$.

We can conclude from the above two cases that $\tau_{k}^{\prime}$ can be
chosen to be $\sec\frac{\pi}{4}+O(k^{-1})=\sqrt{2}+O(k^{-1})$. ∎

Combining Lemma 7 and 9, with the observation that
$\tau_{k}=(1-2\sin(\pi/8))^{-1}+O(k^{-1})$, we can get our main result that
almost all $\mathsf{YY}_{2k}$ are spanners.

######  Theorem 2.

(restated) For any integer $k\geq 42$, $\mathsf{YY}_{2k}$ is a
$t_{k}$-spanner, where
$t_{k}=\tau_{k}^{\prime}\tau_{2k}=\sqrt{2}(1-2\sin(\pi/8))^{-1}+O(k^{-1})=6.03+O(k^{-1})$.

##  5 Conclusion and Future Work

In this paper we proved that Yao-Yao graphs $\mathsf{YY}_{2k}$ are geometric
spanners for $k$ large enough, making a positive progress to the long-standing
Conjecture 1. For Yao-Yao graphs with odd parameters, the resolution of the
conjecture is still elusive and seems to require additional new ideas.

We did not try very hard to optimize the constant stretch ratio for different
$k$ values. Hence, the constant claimed in Theorem 2 may well be further
improved. One potential approach is to use techniques developed in [1].
Obtaining tighter bounds (and lower bounds as well!) is left as an interesting
future work.

We propose some other potential future directions, which are interesting in
their own rights and might lead to sparse spanners with bounded degrees and
small stretch factors.

  * •

Consider the variant of Yao-Yao graphs where the cones are not divided
uniformly. One could expect that such variants are spanners if the apex angles
of the cones are all small. It seems that our techniques in the paper can be
adapted to this situation if the separated cones are centrosymmetric: every
separation ray of polar angle $\varphi$ has a corresponding one at polar angle
$\pi+\varphi$. But the more general case is still open.

  * •

Instead of insisting on one polar division for every node, we can let each
point choose its polar axis individually by uniformly and independently
randomizing a direction. We conjecture that such graphs are also spanners (in
expectation or with high probability) for $k$ large enough.

## References

  * [1] Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian, and Sander Verdonschot.  Continuous Yao graphs.  In Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada, 2014, 2014.
  * [2] Luis Barba, Prosenjit Bose, Mirela Damian, Rolf Fagerberg, Wah Loon Keng, Joseph O’Rourke, André van Renssen, Perouz Taslakian, Sander Verdonschot, and Ge Xia.  New and improved spanning ratios for Yao graphs.  JoCG, 6(2):19–53, 2015.
  * [3] Matthew Bauer and Mirela Damian.  An infinite class of sparse-Yao spanners.  In Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 184–196. SIAM, 2013.
  * [4] Prosenjit Bose, Paz Carmi, Sebastien Collette, and Michiel Smid.  On the stretch factor of convex delaunay graphs.  Journal of computational geometry, 1(1):41–56, 2010.
  * [5] Prosenjit Bose, Mirela Damian, Karim Douïeb, Joseph O’rourke, Ben Seamone, Michiel Smid, and Stefanie Wuhrer.  $\pi$/2-angle Yao graphs are spanners.  International Journal of Computational Geometry & Applications, 22(01):61–82, 2012.
  * [6] Prosenjit Bose, Joachim Gudmundsson, and Michiel H. M. Smid.  Constructing plane spanners of bounded degree and low weight.  Algorithmica, 42(3-4):249–264, 2005.
  * [7] Paul Chew.  There is a planar graph almost as good as the complete graph.  In Proceedings of the second annual symposium on Computational geometry, pages 169–177. ACM, 1986.
  * [8] Artur Czumaj and Hairong Zhao.  Fault-tolerant geometric spanners.  Discrete & Computational Geometry, 32(2):207–230, 2004.
  * [9] Mirela Damian.  A simple Yao-Yao-based spanner of bounded degree.  arXiv preprint arXiv:0802.4325, 2008.
  * [10] Mirela Damian, Nawar Molla, and Val Pinciu.  Spanner properties of $\pi$/2-angle Yao graphs.  In Proc. of the 25th European Workshop on Computational Geometry, pages 21–24. Citeseer, 2009.
  * [11] Mirela Damian and Kristin Raudonis.  Yao graphs span theta graphs.  In Combinatorial Optimization and Applications, pages 181–194. Springer, 2010.
  * [12] David P Dobkin, Steven J Friedman, and Kenneth J Supowit.  Delaunay graphs are almost as good as complete graphs.  In Foundations of Computer Science, 1987., 28th Annual Symposium on, pages 20–26. IEEE, 1987.
  * [13] Nawar M El Molla.  Yao spanners for wireless ad hoc networks.  Master’s thesis, Villanova University, 2009.
  * [14] Lujun Jia, Rajmohan Rajaraman, and Christian Scheideler.  On local algorithms for topology control and routing in ad hoc networks.  In Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, pages 220–229. ACM, 2003.
  * [15] Iyad A Kanj and Ge Xia.  On certain geometric properties of the Yao-Yao graphs.  In Combinatorial Optimization and Applications, pages 223–233. Springer, 2012.
  * [16] Xiang-Yang Li.  Wireless Ad Hoc and Sensor Networks: Theory and Applications.  Cambridge, 6 2008.
  * [17] Xiang-Yang Li, Peng-Jun Wan, and Yu Wang.  Power efficient and sparse spanner for wireless ad hoc networks.  In Computer Communications and Networks, 2001. Proceedings. Tenth International Conference on, pages 564–567. IEEE, 2001.
  * [18] Xiang-Yang Li, Peng-Jun Wan, Yu Wang, and Ophir Frieder.  Sparse power efficient topology for wireless networks.  In System Sciences, 2002. HICSS. Proceedings of the 35th Annual Hawaii International Conference on, pages 3839–3848. IEEE, 2002.
  * [19] Xiang-Yang Li and Yu Wang.  Efficient construction of low weight bounded degree planar spanner.  In Computing and Combinatorics, pages 374–384. Springer, 2003.
  * [20] Giri Narasimhan and Michiel Smid.  Geometric spanner networks.  Cambridge University Press, 2007.
  * [21] David Peleg and Alejandro A Schäffer.  Graph spanners.  Journal of graph theory, 13(1):99–116, 1989.
  * [22] Christian Schindelhauer, Klaus Volbert, and Martin Ziegler.  Geometric spanners with applications in wireless networks.  Computational Geometry, 36(3):197–214, 2007.
  * [23] Andrew Chi-Chih Yao.  On constructing minimum spanning trees in k-dimensional spaces and related problems.  SIAM Journal on Computing, 11(4):721–736, 1982.