Continuous Yao Graphs

Abstract

In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points $S\subset {\mathbb{R}}^2$ and an angle $0<\hat{I}¸\le 2\ddot{I}€$, we define the continuous Yao graph $cY(\hat{I}¸)$ with vertex set $S$ and angle $\hat{I}¸$ as follows. For each $p,q\in S$, we add an edge from $p$ to $q$ in $cY(\hat{I}¸)$ if there exists a cone with apex $p$ and aperture $\hat{I}¸$ such that $q$ is the closest point to $p$ inside this cone. We study the spanning ratio of $cY(\hat{I}¸)$ for different values of $\hat{I}¸$. Using a new algebraic technique, we show that $cY(\hat{I}¸)$ is a spanner when $\hat{I}¸\le 2\ddot{I}€/3$. We believe that this technique may be of independent interest. We also show that $cY(\ddot{I}€)$ is not a spanner, and that $cY(\hat{I}¸)$ may be disconnected for $\hat{I}¸>\ddot{I}€$.

7 pages, 7 figures. Presented at CCCG 2014