×

zbMATH — the first resource for mathematics

\(\pi /2\)-angle Yao graphs are spanners. (English) Zbl 1310.68156
Cheong, Otfried (ed.) et al., Algorithms and computation. 21st international symposium, ISAAC 2010, Jeju, Korea, December 15–17, 2010. Proceedings, Part II. Berlin: Springer (ISBN 978-3-642-17513-8/pbk). Lecture Notes in Computer Science 6507, 446-457 (2010).
Summary: We show that the Yao graph \(Y _{4}\) in the \(L _{2}\) metric is a spanner with stretch factor \(8\sqrt{2}(29+23\sqrt{2})\).
For the entire collection see [Zbl 1202.68003].

MSC:
68R10 Graph theory (including graph drawing) in computer science
05C12 Distance in graphs
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI