# Some Properties of Continuous Yao Graph

Davood Bakhshesh, Mohammad Farshi

► To cite this version:

Davood Bakhshesh, Mohammad Farshi. Some Properties of Continuous Yao Graph. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. pp.44-55, 10.1007/978-3-319-28678-5_4. hal-01446263

HAL Id: hal-01446263

https://inria.hal.science/hal-01446263

Submitted on 25 Jan 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Some properties of continuous Yao graph

Davood Bakhshesh and Mohammad Farshi

Combinatorial and Geometric Algorithms Lab., Department of Computer Science, Yazd University, Yazd, Iran. dbakhshesh@gmail.com, mfarshi@yazd.ac.ir.

**Abstract.** Given a set $S$ of points in the plane and an angle $0 < \theta \le 2\pi$, the continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ defined as follows. For each $p, q \in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a cone with apex $p$ and angular diameter $\theta$ such that $q$ is the closest point to $p$ inside this cone.

In this paper, we prove that for $0 < \theta < \pi/3$ and $t \ge \frac{1}{1-2\sin(\theta/2)}$, the continuous Yao graph $cY(\theta)$ is a $C$-fault-tolerant geometric $t$-spanner where $C$ is the family of convex regions in the plane. Moreover, we show that for every $\theta \le \pi$ and every half-plane $h$, $cY(\theta) \ominus h$ is connected, where $cY(\theta) \ominus h$ is the graph after removing all edges and points inside $h$ from the graph $cY(\theta)$. Also, we show that there is a set of $n$ points in the plane and a convex region $C$ such that for every $\theta \ge \frac{\pi}{3}$, $cY(\theta) \ominus C$ is not connected.

Given a geometric network $G$ and two vertices $x$ and $y$ of $G$, we call a path $P$ from $x$ to $y$ a self-approaching path, if for any point $q$ on $P$, when a point $p$ moves continuously along the path from $x$ to $q$, it always gets closer to $q$. A geometric graph $G$ is self-approaching, if for every pair of vertices $x$ and $y$ there exists a self-approaching path in $G$ from $x$ to $y$. In this paper, we show that there is a set $P$ of $n$ points in the plane such that for some angles $\theta$, Yao graph on $P$ with parameter $\theta$ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on $P$ is a self-approaching graph. Furthermore, in general, we show that for every $\theta > 0$, $cY(\theta)$ is not necessarily a self-approaching graph.

**Keywords:** $t$-spanner, Region-fault tolerant spanner, Continuous Yao graph, Self-approaching graph

## 1 Introduction

Let $S$ be a set of $n$ points in $\mathbb{R}^d$ and let $t \ge 1$ be a real number. A geometric graph is an edge-weighted graph on $S \subseteq \mathbb{R}^d$ such that the weight of each edge is the Euclidean distance between its endpoints. A geometric graph $G$ with vertex set $S$ is called a $t$-spanner for $S$, if for each two points $p$ and $q$ in $S$, there exists a path $Q$ in $G$ between $p$ and $q$ whose length is at most $t$ times $|pq|$, the Euclidean distance between $p$ and $q$. The length of a path is defined to be the sum of the lengths, or weight, of all edges on the path. The path $Q$ is called a $t$-spanner path (or $t$-path) between $p$ and $q$. We denote the length of path $Q$ by $|Q|$. The stretch factor (or dilation) of $G$ is the smallest value of $t$ for which $G$ is a $t$-spanner. The $t$-spanners were introduced by Peleg and Schäffer [14] in the scope
of distributed computing and, then, by Chew [6] in the scope of computational geometry. The *t*-spanners are applicable in many scopes such as graph theory, network topology design, distributed systems, robotics. We refer the reader to [5,8,12,16] for reading about the *t*-spanners and their applications.

The problem of efficient construction of a *t*-spanner for a given point set and a constant $t > 1$ has been studied extensively. One can see the major algorithms for building spanners in the book by Narasimhan and Smid [13].

The Yao graph used by Andrew Yao to construct Euclidean minimum spanning tree on high-dimensional Euclidean space [17]. For a set $S$ of points in the plane, the Yao graph $Y_k$, for $k \ge 2$, is defined as follows. At each point $u \in S$, we draw $k$ cones with apex at $u$ and angle $\frac{2\pi}{k}$. For each point $u \in S$ and cone $C$, we add an edge between $u$ and the closest point to $u$ in $C$. If one chooses $k$ sufficiently large, the Yao graph becomes a *t*-spanner.

In 2014, Barba et al. [3] introduced the *continuous Yao graph* as a variation of Yao graph. The continuous Yao graph $cY(\theta)$ with vertex set $S$ and angle $\theta$ defined as follows: For each $p, q \in S$, we add an edge from $p$ to $q$ in $cY(\theta)$ if there exists a $\theta$-cone, a cone with aperture $\theta$, with apex at $p$ such that $q$ is the closest point to $p$ inside this $\theta$-cone. In continuous Yao graph, for each $u \in S$, we rotate a $\theta$-cone with apex $u$ around $u$ continuously, and connect $u$ to the closest point inside the $\theta$-cone during this rotation. They showed that $cY(\theta)$ has stretch factor at most $1/(1-2\sin(\theta/4))$ for $0 < \theta < 2\pi/3$. Unlike Yao graphs that always have a linear number of edges for any constant $k$, in the worst case, continuous Yao graphs may have a quadratic number of edges. Since $cY(\theta) \subseteq cY(\gamma)$ for any $\theta \ge \gamma$, the continuous Yao graphs are useful in potential applications that require scalability. Moreover, when some rotations apply on the input point set the continuous Yao graphs are invariant [3].

One of the useful properties of a network is *fault tolerance* that is after one or more vertices or edges fail, the remaining graph is still a good network of alive vertices. In particular, a graph $G = (S, E)$ is called *k-vertex fault-tolerant t-spanner* [10] for $S$, denoted by $(k, t)$-VFTS for a given real number $t \ge 1$ and non-negative positive integer $k$, if for each set $S' \subseteq S$ with cardinality of at most $k$, the graph $G \setminus S'$ is a *t*-spanner for $S \setminus S'$. Also, $G$ is called a *k-edge fault-tolerant t-spanner* [10] for $S$, denoted by $(k, t)$-EFTS, if for each set $E' \subseteq E$ with cardinality at most $k$ and for each pair of points $p$ and $q$ in $S$, the graph $G \setminus E'$ contains a path $P$ between $p$ and $q$ with $|P| \le t|P_S|$ where $P_S$ is the shortest path between $p$ and $q$ in the graph $K_S \setminus E'$ in which that $K_S$ is Euclidean complete graph on $S$. Levcopoulos et al. [10] for the first time considered the problem of constructing fault-tolerant spanners in Euclidean spaces efficiently. They proposed three algorithms that construct *k-vertex fault-tolerant spanners*. Some other works on the fault tolerant spanners have been done [7,11].

In 2009, Abam et al. [1] introduced the concept of *region-fault tolerant spanner* for planar point sets. For a fault region $F$ and a geometric graph $G$ on a point set $S$, assume $G \ominus F$ is the remaining graph after removing the vertices of $G$ that lie inside $F$ and all edges that intersect $F$. For a set $\mathcal{F}$ of regions in the plane, an *F-fault tolerant t-spanner* is a geometric graph $G$ on $S$ such that for
any region $F \in \mathcal{F}$, the graph $G \ominus F$ is a $t$-spanner for $\mathcal{G}_c(S) \ominus F$, where $\mathcal{G}_c(S)$ is the complete geometric graph on $S$. They showed for any set of $n$ points in the plane and any family $\mathcal{C}$ of convex regions, one can construct a $\mathcal{C}$-fault tolerant spanner of size $O(n \log n)$ in $O(n \log^2 n)$ time.

In 2013, Alamdari et al. [2] introduced the concept of self-approaching and increasing-chord graph drawings. The problem is that, we are given a graph and we need to check if the graph has a self-approaching or increasing-chord embedding in the Euclidean space.

A geometric graph is self-approaching, if for every pair $s$ and $t$ of vertices of the graph, there exists a self-approaching path from $s$ to $t$, denoted by st-path. A path from $s$ to $t$ is a self-approaching path if for each $q$ on the path, not only the vertices, but any place of the path, if a point $p$ starts at $s$ and moves toward $q$, it always get closer to $q$ in its movement. Also, a graph $G$ is called increasing-chord if, for each pair $u$ and $v$ of its vertices, there exists a path between $u$ and $v$ such that the path is self-approaching both from $u$ to $v$ and from $v$ to $u$. Obviously, an increasing-chord graph is a self-approaching graph.

In the geometric context, the position of the vertices of the graph is fixed, so we just want to know whether a given geometric graph is self-approaching or increasing-chord. One of the interesting properties of these graph is the following. It is known that the stretch factor (or dilation) of any self-approaching graph is at most 5.3332 [9] and the stretch factor of any increasing-chord graph is at most 2.094 [15].

**Our results.** In this paper, we prove the following results. For the rest of the paper $S$ denotes a set of $n$ points in the plane.

1. The continuous Yao graph $cY(\theta)$ on $S$ is a $\mathcal{C}$-fault-tolerant geometric $t$-spanner of $S$, where $0 < \theta < \pi/3$ and $t \ge \frac{1}{1-2\sin(\theta/2)}$.

2. For any $\theta \le \pi$ the graph $cY(\theta) \ominus h$ on $S$ is connected, where $h$ is an arbitrary half-plane in the plane.

3. There is a set of $n$ points in the plane and a convex region $C$ such that for every $\theta \ge \frac{\pi}{3}$, $cY(\theta) \ominus C$ is not connected.

4. There is a set $P$ of $n$ points in the plane such that for some angles $\theta$, Yao graph on $P$ with parameter $\theta$ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on $P$ is a self-approaching graph.

5. For every $\theta > 0$, $cY(\theta)$ is not necessarily a self-approaching graph.

## 2 $cY(\theta)$ is fault-tolerant

In this section, we show that the continuous Yao graph $cY(\theta)$ for $0 < \theta < \pi/3$ and $t \ge \frac{1}{1-2\sin(\theta/2)}$ is a $\mathcal{C}$-fault-tolerant geometric $t$-spanner where $\mathcal{C}$ is the family of convex regions in the plane. Furthermore, we show that for every $\theta \le \pi$ and every half-plane $h$, $cY(\theta) \ominus h$ is connected. Moreover, we show that there is a set of $n$ points such that for a some convex region $C$, $cY(\theta) \ominus C$ is not connected for every $\theta \ge \frac{\pi}{3}$. We need the following lemmas.
**Lemma 1 ([4]).** Let a, b and c be three points such that $|ac| \le |ab|$ and $\angle bac \le \alpha < \pi$. Then

$$|bc| \le |ab| - (1 - 2\sin(\alpha/2))|ac|.$$

**Lemma 2 ([1]).** A geometric graph G on S is a C-fault tolerant t-spanner if and only if it is an H-fault-tolerant t-spanner, where H is the family of all half-planes.

Now, we prove the following theorem:

**Theorem 1.** Let $\theta$ be a real number with $0 < \theta < \pi/3$ and let $t$ be a real number with $t \ge \frac{1}{1-2\sin(\theta/2)}$. For any point set S, the continuous Yao graph $cY(\theta)$ is a C-fault-tolerant geometric t-spanner.

*Proof.* By Lemma 2, it is sufficient to prove that $cY(\theta)$ is an H-fault-tolerant geometric t-spanner.

Let $h$ be an arbitrary half-plane in $\mathcal{H}$. We must show that for each pair of points $p, q \in S$ outside $h$, there is a $t$-path between $p$ and $q$ in $cY(\theta) \ominus h$. The proof is by induction on the rank of distance $|pq|$.

For the base step, suppose that the pair $p$ and $q$ is the closest pair in $cY(\theta) \ominus h$. Without loss of generality, assume the distance between $p$ and $h$ is less than of equal to the distance between $q$ and $h$. Since $p$ and $q$ are outside $h$ and $\theta < \pi/2$, there is a $\theta$-cone $C_p$ with apex at $p$ completely outside $h$ such that $q \in C_p$. Since pair $p$ and $q$ is the closest pair, by the construction of $cY(\theta)$, the edge $(p, q)$ must be in $cY(\theta) \ominus h$. Note that if both $p$ and $q$ have same distance to $h$, then we can choose both $p$ and $q$ as apex, but we have to choose the point such that the corresponding $\theta$-cone does not intersect $h$.

For the induction hypothesis step, suppose for each pair $u, v \in S$ outside $h$ with $|uv| < |pq|$ there is a $t$-path between $u$ and $v$ connecting them in $cY(\theta) \ominus h$.

Now we consider the induction step. Since $p$ and $q$ are outside $h$, there is a $\theta$-cone $C_p$ with apex at $p$ such that $q \in C_p$ (here we assumed that $p$ is closer than $q$ to $h$).

Suppose that $r$ is the closest point to $p$ inside the cone $C_p$ (see Fig. 1). Since $\theta < \pi/3$, $1 - 2\sin(\theta/2) > 0$, and also since $|pr| \le |pq|$, by Lemma 1 we have $|rq| < |pq|$. Therefore, by the induction hypothesis, there is a $t$-path $Q$ between $r$ and $q$ in $cY(\theta) \ominus h$. Now consider the path $P := \{(p, r)\} \cup Q$. Clearly the path $P$ connects $p$ and $q$, and $P$ is in $cY(\theta) \ominus h$. Now by Lemma 1, we have

$$ \begin{aligned} |P| &= |pr| + |Q| \\ &\le |pr| + t|rq| \\ &\le |pr| + t(|pq| - (1 - 2\sin(\theta/2))|pr|) \\ &= t|pq| + (1 - t(1 - 2\sin(\theta/2)))|pr| \\ &\le t|pq| \quad \left( \text{since } t \ge \frac{1}{1 - 2\sin(\theta/2)} \right). \end{aligned} $$

Thus $P$ is a $t$-path in $cY(\theta) \ominus h$ between $p$ and $q$. This completes the proof. $\square$
<figure><img src="image_2.png" /><figcaption>Fig. 1. Illustrating of the proof of Theorem 1.</figcaption></figure>

Note that even though $cY(\theta)$ is a $C$-fault tolerant spanner, it is not necessarily connected. It is because in fault-tolerant spanners, we compare the graph with the complete graph. So if the complete graph after removing points in some regions becomes disconnected, then some of fault-tolerant spanners of the points set might be disconnected. In the following, we show that for every half-plane $h$ in the plane, the graph $cY(\theta) \ominus h$ is a connected graph for every $\theta \le \pi$.

**Lemma 3.** The continuous Yao graph $cY(\pi)$ on each set $S$ contains $CH(S)$, the convex hull of $S$.

*Proof.* Proof is straightforward. □

<figure><img src="image_3.png" /></figure>

**Theorem 2.** For any $\theta \le \pi$ the graph $cY(\theta) \ominus h$ on $S$ is connected, where $h$ is a half-plane.

*Proof.* It is easy to see that for every $\alpha, \beta > 0$, if $\alpha \ge \beta$ then $cY(\alpha) \subseteq cY(\beta)$. So, to prove the theorem, it is sufficient to show that $cY(\pi) \ominus h$ is connected for every half-plane $h$.

Let $h$ be an arbitrary half-plane in the plane. Suppose that $cY(\pi) \ominus h$ is not connected.

Since $cY(\pi) \ominus h$ is disconnected, it has more than one connected component. At least one of the connected components of $cY(\pi) \ominus h$ contains a point from $CH(S)$. Suppose $C$ and $C'$ are two (distinct) connected components of $cY(\pi) \ominus h$ such that at least one of them, say $C$, contains a point from $CH(S)$. If both of $C$ and $C'$ contains a point from $CH(S)$ then by Lemma 3, part of $CH(S)$ which lies outside $h$ is connected which is a contradiction because we assumed that $C$ and $C'$ are distinct connected components of $cY(\pi) \ominus h$.

Now, assume $C'$ contains no vertices on $CH(S)$. Let $x$ be the intersection of boundary of $h$ and $CH(S)$ and let $\ell$ be a line through $x$ and tangent to $C'$ (see Fig. 2). We have two cases.
<figure><img src="image_4.png" /><figcaption>Fig. 2. Illustrating of the proof of Theorem 2: case 1.</figcaption></figure>

**Case 1:** $\ell \cap C'$ contains exactly one point denoted by $y$.

If $x \notin S$ then clearly by the construction of graph $cY(\pi)$, the vertex $y$ should be connected to a vertex of $C$ that is contradiction, since we assumed that $C$ and $C'$ are distinct connected components of $cY(\pi) \ominus h$. Now, suppose that $x \in S$. Since $\ell \cap C'$ contains exactly one point, we can with continuously rotating the line $\ell$ around the point $y$ (in Fig. 2, we rotate $\ell$ counter-clockwise), find a line $\ell'$ such that $\ell' \cap C'$ contains exactly one point that is $y$, and also the point in the intersection of $\ell'$ and boundary $h$ does not belong to $S$. Hence, by the construction of graph $cY(\pi)$, point $y$ should be connected to a vertex of $C$. That is a contradiction with that $C$ and $C'$ are distinct connected components of $cY(\pi) \ominus h$.

**Case 2:** $\ell$ is tangent to $C'$ in at least two points.

We claim that there is a line $\ell'$ that is tangent to exactly one point of $S$ on the convex hull of $C'$ (denoted by $s$). Suppose that $s$ be the farthest point of $S$ on $\ell$ with respect to $x$, and suppose that $r$ be the next point after $s$ on the convex hull of $C'$ in counterclockwise order (see Fig. 3). Let $\ell''$ be a line that through of $s$ and $r$, and let $z$ be the intersection of $\ell''$ and boundary of $h$. Now suppose that $w$ be a point on the segment $xz$ ($w \neq x, z$). Let $\ell'$ be a line that through of $w$ and $s$. Clearly $\ell'$ is tangent to exactly one point of $S$ that is $s$ on the convex hull of $C'$. Now by the construction of $cY(\pi)$, vertex $s$ should be connected to a vertex of connected component of $C$. This contradicts with the assumption that $C$ and $C'$ are distinct connected components of $cY(\pi) \ominus h$.

According to the above mentioned cases, $cY(\pi) \ominus h$ is connected. This completes the proof. □
<figure><img src="image_5.png" /><figcaption>**Fig. 3.** Illustrating of the proof of Theorem 2: case 2.</figcaption></figure>

In the following, we give an example such that for every $\theta \ge \frac{\pi}{3}$, $cY(\theta) \ominus C$ for some convex region $C$ is not necessarily connected.

Assume $P_0 = \{(0,0), (1,\sqrt{3}), (2,0)\}$ which is the vertices of a equilateral triangle. Let $P_i$ be the translation of $P_0$ by value $c \times i$ horizontally where $c$ is a sufficiently large constant positive integer. Here, we consider $c = 10$ (see Fig. 4). We choose the set $P := \cup_{i=0}^{k-1} P_i$.

Let $\theta$ be an angle with $\theta \ge \frac{\pi}{3}$. Consider $cY(\theta)$ on $P$. Note that for $\theta \ge \frac{\pi}{3}$, $cY(\theta)$ on the vertices of an equilateral triangle is exactly the complete graph of their vertices. Now, let $C$ be a convex region such that $C$ only contains the points $(1, \sqrt{3})$, $(2, 0)$, $(10, 0)$ and $(11, \sqrt{3})$ from $P$ (see Fig. 4). Since in the $cY(\theta)$ the vertex $(0, 0)$ is only connected to the vertices $(1, \sqrt{3})$ and $(2, 0)$, clearly in $cY(\theta) \ominus C$ there is no path between $(0, 0)$ and $(12, 0)$. Hence $cY(\theta) \ominus C$ is not connected.

<figure><img src="image_6.png" /><figcaption>**Fig. 4.** An example that $cY(\theta)$ is disconnected after convex region fault.</figcaption></figure>
### 3 $cY(\theta)$ is not self-approaching

In this section, we show that there is a set $P$ of $n$ points in the plane such that for some angles $\theta$, Yao graph on $P$ with parameter $\theta$ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on $P$ is a self-approaching graph. Finally, we show that there is a set of $n$ points in the plane such that for every $\theta > 0$, continuous Yao graph $cY(\theta)$ is not a self-approaching graph.

In the following, we assume that the number of cones is even. With making some modifications, similar results holds for odd number of cones.

Now, let $p = (0,0)$, $q = (1,0)$, $r = (r_1, r_2)$ and $s = (s_1, s_2)$ be four points in the plane. For three points $x, y$ and $z$, let $\angle yxz$ be the angle between the segment $xy$ and $xz$. Now, assume that $\angle qpr = \alpha_1$, $\angle pqr = \alpha_2$, $\angle prq = \alpha_3$, $\angle qps = \beta_1$, $\angle pqs = \beta_2$, $\angle psq = \beta_3$, for some angles $\alpha_i$ and $\beta_i$ with $0 < \alpha_i < \pi/2$ and $0 < \beta_i < \pi/2$ for $i = 1, 2, 3$ (see Fig. 5).

We call the quadrilateral on the four points $p, q, r$ and $s$ a bad quadrilateral if we have the following properties:

1. $|pq| \cos \alpha_1 < |pr| < |pq|$

2. $|pq| \cos \alpha_2 < |qr| < |pq|$

3. $|pq| \cos \beta_1 < |ps| < |pq|$

4. $|pq| \cos \beta_2 < |qs| < |pq|$

<figure><img src="image_7.png" /><figcaption>**Fig. 5.** A bad quadrilateral on the points $p, q, r$ and $s$.</figcaption></figure>

Now, we consider $k$ cones, generated by the $k$-rays through origin, where the $i$th ray has angle $(i-1)\theta$ with the positive $x$-axis. The $i$th cones contains the points $p$ such that the angle of line $op$ with positive $x$-axis is bigger than or equal $(i-1)\theta$ and less than $i\theta$.

Let $V$ be a set of four points $p = (0,0)$, $q = (1,0)$, $r = (r_1, r_2)$ and $s = (s_1, s_2)$ such that the quadrilateral on the vertices $p, q, r$ and $s$ is a bad quadrilateral. It
is easy to see that, for every $\theta$ with $\alpha_1 < \theta \le \frac{\pi}{2}$ such that $\frac{2\pi}{\theta}$ is even number and $\beta_2 < \theta$, the Yao graph $Y_k$ on $V$ where $k = \frac{2\pi}{\theta}$ does not contain the edge $\{p, q\}$ but it contains the edges $\{p, r\}, \{p, s\}, \{q, r\}$ and $\{q, s\}$. So the Yao graph $Y_k$ on the point set $V$ is not a self-approaching graph, since every path from $p$ to $q$ is not a $pq$-path. Indeed, the following lemma shows that $cY(\theta)$ on $V$ is a self-approaching graph.

**Lemma 4.** Let $\alpha_1 + \beta_1 \ge \frac{\pi}{2}$ or $\alpha_2 + \beta_2 \ge \frac{\pi}{2}$. For every $\theta$ such that

a) $\alpha_1 < \theta \le \frac{\pi}{2}$, and

b) $\theta < \alpha_1 + \beta_1$ or $\theta < \alpha_2 + \beta_2$, and

c) $\frac{2\pi}{\theta}$ is even number, and

d) $\beta_2 < \theta$,

continuous Yao graph $cY(\theta)$ on $V$ contains the edge $\{p, q\}$. Furthermore, $cY(\theta)$ on $V$ is a self-approaching graph.

*Proof.* We prove the theorem for the case that $\theta < \alpha_1 + \beta_1$. Similar argument works for the case $\theta < \alpha_2 + \beta_2$.

Since $\theta < \alpha_1 + \beta_1$, by construction of $cY(\theta)$, clearly there is a $\theta$-cone $C$ with apex $p$ that only contains the point $q$. Hence the edge $\{p, q\}$ is in $cY(\theta)$.

On the other hand, the Yao graph on $V$ with angle parameter $\theta$ is a sub-graph of $cY(\theta)$, so the edges $\{p, r\}, \{p, s\}, \{q, r\}$ and $\{q, s\}$ are in $cY(\theta)$. So, we only need to show that there is a self-approaching path from $r$ to $s$ and a self-approaching path from $s$ to $r$.

Since $\alpha_1 + \beta_1 \ge \frac{\pi}{2}$ or $\alpha_2 + \beta_2 \ge \frac{\pi}{2}$, the path $r \to q \to s$ or $r \to p \to s$ is an $rs$-path and in the reverse direction is an $sr$-path. So there is an $xy$-path between all ordered pairs $\{x, y\}$ for $x, y \in V$. Hence, $cY(\theta)$ is a self-approaching graph on $V$. This completes the proof. $\square$

Next, we will give another point set such that the Yao graph on the point set is not self-approaching graph, but the continuous Yao graph is a self-approaching graph.

Let $P$ be a set of $n$ points as follows:

$$P = V \cup \{x_1, x_2, \dots, x_{n-4}\}, \qquad (1)$$

with $x_j = (c + j, 0)$ for $1 \le j \le n - 4$ where $c$ is a sufficiently large constant positive integer. Here, we consider $c = 19$ (see Fig. 6).

Now, using Lemma 4 we can easily find the following result.

**Lemma 5.** Let $\alpha_1 + \beta_1 \ge \frac{\pi}{2}$ or $\alpha_2 + \beta_2 \ge \frac{\pi}{2}$. For every $\theta$ such that

a) $\alpha_1 < \theta \le \frac{\pi}{2}$, and

b) $\theta < \alpha_1 + \beta_1$ or $\theta < \alpha_2 + \beta_2$, and

c) $\frac{2\pi}{\theta}$ is even number, and

d) $\beta_2 < \theta$,

continuous Yao graph $cY(\theta)$ on $P$ is self-approaching and $Y_k$ is not a self-approaching for $k = \frac{2\pi}{\theta}$.
<figure><img src="image_8.png" /><figcaption>Fig. 6. The set P with n = 8.</figcaption></figure>

Note that there are some point set that satisfy the conditions mentioned in above lemmas. For example, let $V = \{p, q, r, s\}$ with $p = (0,0), q = (1,0), r = (0.7839, 0.4422), s = (0.2161, -0.4422)$, and suppose that $k = 4$ and $\theta = \frac{\pi}{2}$. We can easily verify that the quadrilateral on the points of V is a bad quadrilateral. Moreover we have

$$ \alpha_1 = 29.4271^{\circ}, \alpha_2 = 63.9535^{\circ}, \alpha_3 = 86.6198^{\circ}, $$

$$ \beta_1 = 29.4271^{\circ}, \beta_2 = 63.9535^{\circ}, \beta_3 = 86.6198^{\circ}. $$

Now, suppose that $P = V \cup \{x_1, x_2, \dots, x_{n-4}\}$ where $x_i = (19 + i, 0)$. This point set satisfies Lemma 5.

At the first view, it seems that the continuous Yao graph is a self-approaching graph, but this is not true in general. Next, we give a point set such that for each $\theta$, the continuous Yao graph $cY(\theta)$ on the point set is not a self-approaching graph.

**Theorem 3.** There is a set $P$ of $n$ points such that for every $\theta > 0$, $cY(\theta)$ on $P$ is not a self-approaching graph.

*Proof.* We prove the theorem for $0 < \theta \le \frac{2\pi}{3}$. Since for every $\alpha_1$ and $\alpha_2$ with $\alpha_1 \le \alpha_2$ we have $cY(\alpha_2) \subseteq cY(\alpha_1)$, the theorem holds for every $\theta > 0$.

Consider two points $p = (0,0)$ and $q = (1,0)$. Let $C$ be a circle centered at the midpoint of the segment $pq$, with radius $\frac{1}{2}$. Let $D_p$ and $D_q$ be circles respectively centered at $p$ and $q$ with radius one. Let $\ell$ be the perpendicular bisector of segment $pq$ (see Fig. 7).

Consider $x$ and $y$ as points outside $C$ and inside $D_p \cap D_q$ such that $\angle xpq < \frac{\theta}{2}$ and $\angle ypq < \frac{\theta}{2}$. Let $x'$ and $y'$ be the symmetries of $x$ and $y$ with respect to line $\ell$, respectively.

Now let $V = \{p, q, x, y, x', y'\}$, and consider $cY(\theta)$ on $V$. Since $\angle xpy = \angle x'qy' < \theta$, $cY(\theta)$ does not contain the edge $\{p, q\}$. So, by our selection of points $x, y, x'$ and $y'$, there is no self-approach path between $p$ and $q$. Hence, $cY(\theta)$ on $V$ is not self-approaching.

One can extend this point set to a point set with arbitrary number of points such that $cY(\theta)$ is not a self-approaching graph of the point set. To this end, one
<figure><img src="image_9.png" /><figcaption>Fig. 7. Illustrating of the proof of Theorem 3.</figcaption></figure>

can add any point to V which is sufficiently far from the points in the original set V, because adding points which are far can not help in making a self-approaching path from p to q. □

**4 Concluding remarks**

We proved that for $0 < \theta < \pi/3$ and $t \ge \frac{1}{1-2\sin(\theta/2)}$, the continuous Yao graph $cY(\theta)$ is a $C$-fault-tolerant geometric $t$-spanner. Furthermore, we showed that for every $\theta \le \pi$ and every half-plane $h$, $cY(\theta) \ominus h$ is connected. Finally, we showed that for every $\theta > 0$, $cY(\theta)$ is not necessarily a self-approaching graph. The question whether $cY(\theta)$ for $\frac{\pi}{3} \le \theta \le \pi$ is a $C$-fault-tolerant geometric spanner with constant stretch factor remains open.

**References**

1. Abam, M.A., de Berg, M., Farshi, M., Gudmundsson, J.: Region-fault tolerant geometric spanners. Discrete and Computational Geometry 41(4), 556–582 (2009)

2. Alamdari, S., Chan, T.M., Grant, E., Lubiw, A., Pathak, V.: Self-approaching graphs. In: International Symposium on Graph Drawing. pp. 260–271. Springer (2013)

3. Barba, L., Bose, P., de Carufel, J.L., Damian, M., Fagerberg, R., van Renssen, A., Taslakian, P., Verdonschot, S.: Continuous Yao graphs. In: Proceedings of the
26th Canadian Conference on Computational Geometry. p. tbd. CCCG'14 (August 2014)

4. Barba, L., Bose, P., Damian, M., Fagerberg, R., Keng, W.L., O'Rourke, J., van Renssen, A., Taslakian, P., Verdonschot, S., Xia, G.: New and improved spanning ratios for Yao graphs. In: Annual ACM Symposium on Computational Geometry. p. 30. ACM (2014)

5. Chandra, B., Das, G., Narasimhan, G., Soares, J.: New sparseness results on graph spanners. In: Proceedings of the eighth Annual ACM Symposium on Computational Geometry. pp. 192–201. ACM (1992)

6. Chew, P.: There is a planar graph almost as good as the complete graph. In: Proceedings of the second Annual ACM Symposium on Computational Geometry. pp. 169–177. ACM (1986)

7. Czumaj, A., Zhao, H.: Fault-tolerant geometric spanners. Discrete and Computational Geometry 32(2), 207–230 (2004)

8. Eppstein, D.: Spanning trees and spanners. Handbook of computational geometry pp. 425–461 (1999)

9. Icking, C., Klein, R., Langetepe, E.: Self-approaching curves. In: Mathematical Proceedings of the Cambridge Philosophical Society. vol. 125, pp. 441–453. Cambridge Univ Press (1999)

10. Levcopoulos, C., Narasimhan, G., Smid, M.: Improved algorithms for constructing fault-tolerant spanners. Algorithmica 32(1), 144–156 (2002)

11. Lukovszki, T.: New results on fault tolerant geometric spanners. In: Algorithms and Data Structures, pp. 193–204. Springer (1999)

12. Lukovszki, T.: New results on geometric spanners and their applications. Ph.D. thesis, Heinz Nixdorf Institute and Department of Mathematics and Computer Science, Paderborn University, Paderborn, Germany (1999)

13. Narasimhan, G., Smid, M.: Geometric spanner networks. Cambridge University Press (2007)

14. Peleg, D., Schäffer, A.A.: Graph spanners. Journal of graph theory 13(1), 99–116 (1989)

15. Rote, G.: Curves with increasing chords. In: Mathematical Proceedings of the Cambridge Philosophical Society. vol. 115, pp. 1–12. Cambridge University Press (1994)

16. Smid, M.: Closest point problems in computational geometry. Handbook on Computational Geometry (1997)

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