Continuous Yao graphs
In this paper, we introduce a variation of the wellstudied Yao graphs. Given a set of points S ⊂ ℝ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 (θ) may be disconnected for θ > π.
|Conference||26th Canadian Conference on Computational Geometry, CCCG 2014|
Barba, L. (Luis), Bose, P, De Carufel, J.-L. (Jean-Lou), Damian, M. (Mirela), Fagerberg, R. (Rolf), Van Renssen, A. (André), … Verdonschot, S. (Sander). (2014). Continuous Yao graphs. Presented at the 26th Canadian Conference on Computational Geometry, CCCG 2014.