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.
Type de document :
Communication dans un congrès
Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.44-55, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_4〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01446263
Contributeur : Hal Ifip <>
Soumis le : mercredi 25 janvier 2017 - 16:50:54
Dernière modification le : jeudi 26 janvier 2017 - 10:20:45
Document(s) archivé(s) le : mercredi 26 avril 2017 - 18:28:56

Fichier

 Accès restreint
Fichier visible le : 2019-01-01

Connectez-vous pour demander l'accès au fichier

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Davood Bakhshesh, Mohammad Farshi. Some Properties of Continuous Yao Graph. Mohammed Taghi Hajiaghayi; Mohammad Reza Mousavi. 1st International Conference on Theoretical Computer Science (TTCS), Aug 2015, Tehran, Iran. Lecture Notes in Computer Science, LNCS-9541, pp.44-55, 2016, Topics in Theoretical Computer Science. 〈10.1007/978-3-319-28678-5_4〉. 〈hal-01446263〉

Partager

Métriques

Consultations de la notice

29