### Abstract

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points S⊂R^{2} and an angle 0<θ⩽2π, we define the continuous Yao graph cY(θ) with vertex set S and angle θ as follows. For each p,q∈S, we add an edge from p to q in cY(θ) if there exists a cone with apex p and aperture θ such that q is a closest point to p inside this cone. We study the spanning ratio of cY(θ) for different values of θ. Using a new algebraic technique, we show that cY(θ) is a spanner when θ⩽2π/3. We believe that this technique may be of independent interest. We also show that cY(π) is not a spanner, and that cY(θ) may be disconnected for θ>π, but on the other hand is always connected for θ⩽π. Furthermore, we show that cY(θ) is a region-fault-tolerant geometric spanner for convex fault regions when θ<π/3. For half-plane faults, cY(θ) remains connected if θ⩽π. Finally, we show that cY(θ) is not always self-approaching for any value of θ.

Original language | English |
---|---|

Journal | Computational Geometry: Theory and Applications |

Volume | 67 |

Pages (from-to) | 42-52 |

ISSN | 0925-7721 |

DOIs | |

Publication status | Published - 2018 |

### Fingerprint

### Keywords

- Self-approaching graph
- Spanner
- Spanning ratio
- Yao graph

### Cite this

*Computational Geometry: Theory and Applications*,

*67*, 42-52. https://doi.org/10.1016/j.comgeo.2017.10.002