2014/08/18 by Luis Barba, Prosenjit Bose, Barba, Luis +13 · 1 citation
Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1408.4099
openalex publication_date 2014/08/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
In this paper, we introduce a variation of the well-studied 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 θ> π.