Special Issue: Selected Papers from the 21st Annual International Symposium on Algorithms and Computation by O. Cheong and Y. OkamotoNo Access
π/2-ANGLE YAO GRAPHS ARE SPANNERS
https://doi.org/10.1142/S0218195912600047Cited by:20
Abstract
We show that the Yao graph Y4 in the L2 metric is a spanner with stretch factor 
. Enroute to this, we also show that the Yao graph 
in the L∞ metric is a plane spanner with stretch factor 8.
References
- P. Bose, M. Damian, K. Douïeb, J. O'Rourke, B. Seamone, M. Smid and S. Wuhrer, π/2-angle Yao graphs are spanners, Technical Report (2010) , arXiv:1001.2913v1 . Google Scholar
- Comput. Geom.: Theor. Appl. 29, 233 (2004), DOI: 10.1016/j.comgeo.2004.04.003. Crossref, ISI, Google Scholar
- M. Damian, N. Molla and V. Pinciu, Spanner properties of π/2-angle Yao graphs, Proc. 25th European Workshop on Computational Geometry, March 2009, pp. 21–24 . Google Scholar
- M. Damian and K. Raudonis, Yao graphs span theta graphs, Proc. 4th Annual Int. Conf. Combinatorial Optimization and Applications, December 2010, pp. 181–194 . Google Scholar
M. Fischer , T. Lukovszki and M. Ziegler , Geometric searching in walkthrough animations with weak spanners in real time, Proc. 6th Annual European Symp. Algorithms (1998) pp. 163–174. Google Scholar- N. Molla, Yao spanners for wireless ad hoc networks, M.S. thesis, Department of Computer Science, Villanova University, December 2009 . Google Scholar
- Portugaliae Math. 10(3), 121 (1951). Google Scholar
- SIAM J. Comput. 11(4), 721 (1982), DOI: 10.1137/0211059. Crossref, ISI, Google Scholar
| Remember to check out the Most Cited Articles! |
|---|
|
Check out these titles in image analysis! |
