Continuous Yao Graphs

Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, André van Renssen, Perouz Taslakian, Sander Verdonschot

Publikation: Kapitel i bog/rapport/konference-proceedingKapitel i bogForskningpeer review


In this paper, we introduce a variation of the wellstudied 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 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 θ > π.
TitelProceedings of the 26th Canadian Conference on Computational Geometry
StatusUdgivet - 2014
Begivenhed26th Canadian Conference on Computational Geometry - Halifax, Nova Scotia, Canada
Varighed: 11. aug. 201413. aug. 2014
Konferencens nummer: 26


Konference26th Canadian Conference on Computational Geometry
ByHalifax, Nova Scotia


Dyk ned i forskningsemnerne om 'Continuous Yao Graphs'. Sammen danner de et unikt fingeraftryk.