Routing on Heavy Path WSPD Spanners

It appears your Web browser is not configured to display PDF files. Download adobe Acrobat or click here to download the PDF file.

Click here to download the PDF file.


Tuttle, Tyler James




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.


Computer Science




Carleton University

Thesis Degree Name: 

Master of Computer Science: 

Thesis Degree Level: 


Thesis Degree Discipline: 

Computer Science

Parent Collection: 

Theses and Dissertations

Items in CURVE are protected by copyright, with all rights reserved, unless otherwise indicated. They are made available with permission from the author(s).