## Abstrakt

In this paper, we introduce a variation of the wellstudied Yao graphs. Given a set of points S ⊂ R

be disconnected for θ > π.

^{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 the 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 (θ) maybe disconnected for θ > π.

Originalsprog | Engelsk |
---|---|

Titel | Proceedings of the 26th Canadian Conference on Computational Geometry |

Forlag | CCCG |

Publikationsdato | 2014 |

Sider | 100-106 |

Status | Udgivet - 2014 |

Begivenhed | 26th Canadian Conference on Computational Geometry - Halifax, Nova Scotia, Canada Varighed: 11. aug. 2014 → 13. aug. 2014 Konferencens nummer: 26 |

### Konference

Konference | 26th Canadian Conference on Computational Geometry |
---|---|

Nummer | 26 |

Land/Område | Canada |

By | Halifax, Nova Scotia |

Periode | 11/08/2014 → 13/08/2014 |