%0 Conference Proceedings
%T Some Properties of Continuous Yao Graph
%+ Yazd University
%A Bakhshesh, Davood
%A Farshi, Mohammad
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Conference on Theoretical Computer Science (TTCS)
%C Tehran, Iran
%Y Mohammed Taghi Hajiaghayi
%Y Mohammad Reza Mousavi
%3 Topics in Theoretical Computer Science
%V LNCS-9541
%P 44-55
%8 2015-08-26
%D 2015
%R 10.1007/978-3-319-28678-5_4
%K t-spanner
%K Region-fault tolerant spanner
%K Continuous Yao graph
%K Self-approaching graph
%Z Computer Science [cs]Conference papers
%X Given a set <i>S</i> of points in the plane and an angle $0 < \theta \le 2\pi $, the continuous Yao graph $cY (\theta )$ with vertex set <i>S</i> and angle $\theta $ defined as follows. For each $p, q \in S$, we add an edge from <i>p</i> to <i>q</i> in $cY (\theta )$ if there exists a cone with apex <i>p</i> and angular diameter $\theta $ such that <i>q</i> is the closest point to <i>p</i> 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 <i>h</i>, $cY(\theta )\ominus h$ is connected, where $cY(\theta )\ominus h$ is the graph after removing all edges and points inside <i>h</i> from the graph $cY(\theta )$. Also, we show that there is a set of <i>n</i> points in the plane and a convex region <i>C</i> such that for every $\theta \ge \frac{\pi }{3}$, $cY(\theta )\ominus C$ is not connected.Given a geometric network <i>G</i> and two vertices <i>x</i> and y of <i>G</i>, we call a path <i>P</i> from <i>x</i> to y a self-approaching path, if for any point <i>q</i> on <i>P</i>, when a point <i>p</i> moves continuously along the path from <i>x</i> to <i>q</i>, it always get closer to <i>q</i>. A geometric graph <i>G</i> is self-approaching, if for every pair of vertices <i>x</i> and <i>y</i> there exists a self-approaching path in <i>G</i> from <i>x</i> to <i>y</i>. In this paper, we show that there is a set <i>P</i> of <i>n</i> points in the plane such that for some angles $\theta $, Yao graph on <i>P</i> with parameter $\theta $ is not a self-approaching graph. Instead, the corresponding continuous Yao graph on <i>P</i> is a self-approaching graph. Furthermore, in general, we show that for every $\theta >0$, $cY(\theta )$ is not necessarily a self-approaching graph.
%G English
%Z TC 1
%Z WG 1.8
%2 https://inria.hal.science/hal-01446263/document
%2 https://inria.hal.science/hal-01446263/file/385217_1_En_4_Chapter.pdf
%L hal-01446263
%U https://inria.hal.science/hal-01446263
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC1
%~ IFIP-LNCS-9541
%~ IFIP-WG1-8
%~ IFIP-TTCS