Continuous Yao graphs

Davood Bakhshesh, Luis Barba, Prosenjit Bose, Jean Lou De Carufel, Mirela Damian, Rolf Fagerberg, Mohammad Farshi*, André van Renssen, Perouz Taslakian, Sander Verdonschot

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

91 Downloads (Pure)

Abstract

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 θ.

Original languageEnglish
JournalComputational Geometry: Theory and Applications
Volume67
Pages (from-to)42-52
ISSN0925-7721
DOIs
Publication statusPublished - 2018

    Fingerprint

Keywords

  • Self-approaching graph
  • Spanner
  • Spanning ratio
  • Yao graph

Cite this

Bakhshesh, D., Barba, L., Bose, P., De Carufel, J. L., Damian, M., Fagerberg, R., Farshi, M., van Renssen, A., Taslakian, P., & Verdonschot, S. (2018). Continuous Yao graphs. Computational Geometry: Theory and Applications, 67, 42-52. https://doi.org/10.1016/j.comgeo.2017.10.002