Conference Papers Year : 2016

Some Properties of Continuous Yao Graph

Davood Bakhshesh
  • Function : Author
  • PersonId : 999377
Mohammad Farshi
  • Function : Author
  • PersonId : 999378

Abstract

Given a set S of points in the plane and an angle 0<θ2π, the continuous Yao graph cY(θ) with vertex set S and angle θ defined as follows. For each p,qS, we add an edge from p to q in cY(θ) if there exists a cone with apex p and angular diameter θ such that q is the closest point to p inside this cone.In this paper, we prove that for 0<θ<π/3 and t112sin(θ/2), the continuous Yao graph cY(θ) 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 θπ and every half-plane h, cY(θ)h is connected, where cY(θ)h is the graph after removing all edges and points inside h from the graph cY(θ). Also, we show that there is a set of n points in the plane and a convex region C such that for every θπ3, cY(θ)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 θ, Yao graph on P with parameter θ 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 θ>0, cY(θ) is not necessarily a self-approaching graph.

Fichier principal
Vignette du fichier
385217_1_En_4_Chapter.pdf (343) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

hal-01446263 , version 1 (25-01-2017)

Licence

Identifiers

Cite

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⟩
84 View
94 Download

Altmetric

Share

  • More