No Access

Spanning Properties of Yao and $𝜃$ -Graphs in the Presence of Constraints

Prosenjit Bose

School of Computer Science, Carleton University, 1125 Colonel By Drive, Ottawa, K1S 5B6, Canada

E-mail Address: [email protected]

Search for more papers by this author

and

André van Renssen

School of Computer Science, University of Sydney, 2006, NSW, Australia

E-mail Address: [email protected]

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S021819591950002XCited by:6 (Source: Crossref)

Abstract

We present improved upper bounds on the spanning ratio of constrained $𝜃$ -graphs with at least 6 cones and constrained Yao-graphs with 5 or at least 7 cones. Given a set of points in the plane, a Yao-graph partitions the plane around each vertex into $m$ disjoint cones, each having aperture $𝜃 = 2 π / m$ , and adds an edge to the closest vertex in each cone. Constrained Yao-graphs have the additional property that no edge properly intersects any of the given line segment constraints. Constrained $𝜃$ -graphs are similar to constrained Yao-graphs, but use a different method to determine the closest vertex.

We present tight bounds on the spanning ratio of a large family of constrained $𝜃$ -graphs. We show that constrained $𝜃$ -graphs with $4 k + 2$ ( $k \geq 1$ and integer) cones have a tight spanning ratio of $1 + 2 sin (𝜃 / 2)$ , where $𝜃$ is $2 π / (4 k + 2)$ . We also present improved upper bounds on the spanning ratio of the other families of constrained $𝜃$ -graphs. These bounds match the current upper bounds in the unconstrained setting.

We also show that constrained Yao-graphs with an even number of cones ( $m \geq 8$ ) have spanning ratio at most $1 / (1 - 2 sin (𝜃 / 2))$ and constrained Yao-graphs with an odd number of cones ( $m \geq 5$ ) have spanning ratio at most $1 / (1 - 2 sin (3 𝜃 / 8))$ . As is the case with constrained $𝜃$ -graphs, these bounds match the current upper bounds in the unconstrained setting, which implies that like in the unconstrained setting using more cones can make the spanning ratio worse.

Extended abstracts containing results in this paper appeared in LATIN 2014 and CCCG 2014.

Communicated by J. S. B. Mitchell

Keywords:

References

1. O. Aichholzer et al., Theta-3 is connected, Computational Geometry: Theory and Applications Special Issue for CCCG 2013 47(9) (2014) 910–917. Google Scholar
2. I. Althöfer et al., On sparse spanners of weighted graphs, Discr. Comput. Geom. 9(1) (1993) 81–100. Web of Science, Google Scholar
3. L. Barba et al., New and improved spanning ratios for Yao graphs, J. Comput. Geom. Special Issue for SoCG 2014 6(2) (2015) 19–53. Google Scholar
4. L. Barba et al., On the stretch factor of the theta-4 graph, in Proc. 13th Algorithms and Data Structures Symposium (WADS 2013), Vol. 8037, Lecture Notes in Computer Science (2013), pp. 109–120. Google Scholar
5. P. Bose et al., $π / 2$ -angle Yao graphs are spanners, arXiv e-prints, 2010, arXiv:1001.2913 [cs.CG]. Google Scholar
6. P. Bose et al., $π / 2$ -angle Yao graphs are spanners, Int. J. Comput. Geom. Appl. 22(1) (2012) 61–82. Link, Web of Science, Google Scholar
7. P. Bose et al., Towards tight bounds on theta-graphs: More is not always better, Theor. Comput. Sci. 616 (2016) 70–93. Web of Science, Google Scholar
8. P. Bose et al., On plane constrained bounded-degree spanners, Algorithmica 81(4) (2019) 1392–1415. Web of Science, Google Scholar
9. P. Bose and J. M. Keil, On the stretch factor of the constrained Delaunay triangulation, in Proc. 3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2006) (2006), pp. 25–31. Google Scholar
10. P. Bose et al., Approximating geometric bottleneck shortest paths, Computational Geometry: Theory and Applications 29(3) (2004) 233–249. Web of Science, Google Scholar
11. P. Bose et al., The $𝜃_{5}$ -graph is a spanner, Computational Geometry: Theory and Applications 48(2) (2015) 108–119. Web of Science, Google Scholar
12. P. Bose and M. Smid, On plane geometric spanners: A survey and open problems, Computational Geometry: Theory and Applications 46(7) (2013) 818–830. Web of Science, Google Scholar
13. K. Clarkson, Approximation algorithms for shortest path motion planning, in Proc. 19th Annual ACM Symposium on Theory of Computing (STOC 1987) (1987), pp. 56–65. Google Scholar
14. M. Damian and K. Raudonis, Yao graphs span theta graphs, Discr. Math. Algorith. Appl. 4(02) (2012) 1250024, 16 pp. Google Scholar
15. G. Das, The visibility graph contains a bounded-degree spanner, in Proc. 9th Canadian Conference on Computational Geometry (CCCG 1997) (1997), pp. 70–75. Google Scholar
16. N. M. El Molla, Yao spanners for wireless ad hoc networks, Master’s thesis, Villanova University (2009). Google Scholar
17. B. E. Flinchbaugh and L. K. Jones, Strong connectivity in directional nearest-neighbor graphs, SIAM J. Algebraic Discr. Meth. 2(4) (1981) 461–463. Web of Science, Google Scholar
18. Darryl Hill, Personal communication (2017). Google Scholar
19. J. Keil, Approximating the complete Euclidean graph, in Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT 1988) (1988), pp. 208–213. Google Scholar
20. G. Narasimhan and M. Smid, Geometric Spanner Networks (Cambridge University Press, 2007). Google Scholar
21. J. Ruppert and R. Seidel, Approximating the $d$ -dimensional complete Euclidean graph, in Proc. 3rd Canadian Conference on Computational Geometry (CCCG 1991) (1991), pp. 207–210. Google Scholar
22. A. C. C. Yao, On constructing minimum spanning trees in $k$ -dimensional spaces and related problems, SIAM J. Comput. 11(4) (1982) 721–736. Web of Science, Google Scholar