Continuous Yao graphs
In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points S⊂R2 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 θ.
|Keywords||Self-approaching graph, Spanner, Spanning ratio, Yao graph|
Bakhshesh, D. (Davood), Barba, L. (Luis), Bose, P, De Carufel, J.-L. (Jean-Lou), Damian, M. (Mirela), Fagerberg, R. (Rolf), … Verdonschot, S. (Sander). (2018). Continuous Yao graphs. Computational Geometry, 67, 42–52. doi:10.1016/j.comgeo.2017.10.002