π/2-ANGLE YAO GRAPHS ARE SPANNERS
Authors:
- 1 February 2012
- journal article
- research article
- Published by World Scientific Pub Co Pte Ltd in International Journal of Computational Geometry & Applications
- Vol. 22 (01) , 61-82
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.Keywords
All Related Versions
This publication has 2 references indexed in Scilit:
- Approximating geometric bottleneck shortest pathsComputational Geometry, 2004
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related ProblemsSIAM Journal on Computing, 1982