Continuous Yao Graphs

Abstract

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.