Creator:
Date:
Abstract:
In this thesis, we present a construction of a spanner on a set of $n$ points in $\R^d$ that we call a heavy path WSPD spanner. The construction is parameterized by a constant $s>2$. The size of the graph is $O(s^dn)$ and the spanning ratio is at most $1+2/s+2/(s-1)$. We also show that this graph has a hop spanning ratio of at most $2\lg{n}+1$. We present a memoryless local routing algorithm for heavy path WSPD spanners. A vertex $v$ of the graph stores $O(\deg(v)\log{n})$ bits of information. The routing ratio is at most $1+4/s+1/(s-1)$ and at least $1+4/s$. The number of edges on the routing path is bounded by $2\lg{n}+1$. We then show that the construction and routing algorithm can be generalized to metric spaces of bounded doubling dimension. The spanning and hop spanning ratios are unchanged. The routing ratio becomes at most $1+(2+\frac{\tau}{\tau-1})/s+1/(s-1)$, where $\tau\ge11$ is a constant.