New and improved spanning ratios for Yao graphs

Abstract: For a set of points in the plane and a fixed integer

k > 0

, the Yao graph

Y_{k}

partitions the space around each point into

k

equiangular cones of angle

h e t a = 2 p i / k

, and connects each point to a nearest neighbor in each cone. It is known for all Yao graphs, with the sole exception of

Y_{5}

, whether or not they are geometric spanners. In this paper we close this gap by showing that for odd

k g e q 5

, the spanning ratio of

Y_{k}

is at most

1 / (1 - 2 s i n (3 h e t a / 8))

, which gives the first constant upper bound for

Y_{5}

, and is an improvement over the previous bound of

1 / (1 - 2 s i n (h e t a / 2))

for odd

k g e q 7

. We further reduce the upper bound on the spanning ratio for

Y_{5}

from

10.9

to

2 + s q r t 3 a p p r o x 3.74

, which falls slightly below the lower bound of

3.79

established for the spanning ratio of

T h e t a_{5}

(

T h e t a

-graphs differ from Yao graphs only in the way they select the closest neighbor in each cone). This is the first such separation between a Yao and

T h e t a

-graph with the same number of cones. We also give a lower bound of

2.87

on the spanning ratio of

Y_{5}

. Finally, we revisit the

Y_{6}

graph, which plays a particularly important role as the transition between the graphs (

k > 6

) for which simple inductive proofs are known, and the graphs (

k l e 6

) whose best spanning ratios have been established by complex arguments. Here we reduce the known spanning ratio of

Y_{6}

from

17.6

to

5.8

, getting closer to the spanning ratio of 2 established for

T h e t a_{6}

.

Recommendations

Cited in

(14)

This page was built for publication: New and improved spanning ratios for Yao graphs