Continuous Yao graphs
| Autor: | Jean-Lou De Carufel, Perouz Taslakian, Sander Verdonschot, Davood Bakhshesh, Luis Barba, Mirela Damian, Mohammad Farshi, André van Renssen, Rolf Fagerberg, Prosenjit Bose |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Vertex (graph theory)
Control and Optimization Geometric spanner 010102 general mathematics Spanning ratio Spanner Regular polygon 0102 computer and information sciences 01 natural sciences Graph Computer Science Applications Self-approaching graph Combinatorics Computational Mathematics Computational Theory and Mathematics Yao graph 010201 computation theory & mathematics Closest point Geometry and Topology 0101 mathematics Algebraic number Mathematics |
| Zdroj: | 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, vol. 67, pp. 42-52 . https://doi.org/10.1016/j.comgeo.2017.10.002 |
| DOI: | 10.1016/j.comgeo.2017.10.002 |
| Popis: | In this paper, we introduce a variation of the well-studied Yao graphs. Given a set of points S ⊂ R 2 and an angle 0 θ ⩽ 2 π , we define the continuous Yao graph c Y ( θ ) with vertex set S and angle θ as follows. For each p , q ∈ S , we add an edge from p to q in c Y ( θ ) 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 c Y ( θ ) for different values of θ. Using a new algebraic technique, we show that c Y ( θ ) is a spanner when θ ⩽ 2 π / 3 . We believe that this technique may be of independent interest. We also show that c Y ( π ) is not a spanner, and that c Y ( θ ) may be disconnected for θ > π , but on the other hand is always connected for θ ⩽ π . Furthermore, we show that c Y ( θ ) is a region-fault-tolerant geometric spanner for convex fault regions when θ π / 3 . For half-plane faults, c Y ( θ ) remains connected if θ ⩽ π . Finally, we show that c Y ( θ ) is not always self-approaching for any value of θ. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|