Spanning Properties of Theta-Theta-6

Abstract

We show that, unlike the Yao-Yao graph $Y{Y}_6$, the Theta-Theta graph $\Theta {\Theta }_6$ defined by six cones is a spanner for sets of points in convex position. We also show that, for sets of points in non-convex position, the spanning ratio of $\Theta {\Theta }_6$ is unbounded.

13 pages, 9 figures