Skip to Main content Skip to Navigation
Conference papers

Some Properties of Continuous Yao Graph

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 $\mathcal {C}$-fault-tolerant geometric t-spanner where $\mathcal {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 get 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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01446263
Contributor : Hal Ifip <>
Submitted on : Wednesday, January 25, 2017 - 4:50:54 PM
Last modification on : Thursday, January 26, 2017 - 10:20:45 AM
Long-term archiving on: : Wednesday, April 26, 2017 - 6:28:56 PM

File

385217_1_En_4_Chapter.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

91

Files downloads

130