The well-separated pair decomposition (WSPD) of the complete Euclidean graph
defined on points in R 2 , introduced by Callahan and Kosaraju [JACM, 42 (1): 67-90,
1995], is a technique for partitioning the edges of the complete graph based on length
into a linear number of sets. Among the many different applications of WSPDs,
Callahan and Kosaraju proved that the sparse subgraph that results by selecting an
arbitrary edge from each set (called WSPD-spanner) is a 1 + 8/(s − 4)-spanner, where
s > 4 is the separation ratio used for partitioning the edges.
Although competitive local-routing strategies exist for various spanners such as
Yao-graphs, Θ-graphs, and variants of Delaunay graphs, few local-routing strategies
are known for any WSPD-spanner. Our main contribution is a local-routing algorithm
with a near-optimal competitive routing ratio of 1 + O(1/s) on a WSPD-spanner.
Specifically, using Callahan and Kosaraju’s fair split-tree, we show how to build a
WSPD-spanner with spanning ratio 1 + 4/s + 4/(s − 2) which is a slight improvement
over 1 + 8/(s − 4). We then present a 2-local and a 1-local routing algorithm on
this spanner with competitive routing ratios of 1 + 6/(s − 2) + 4/s and 1 + 8/(s −
2) + 4/s + 8/s 2 , respectively. Moreover, we prove that there exists a point set for
which our WSPD-spanner has a spanning ratio of at least 1 + 8/s, thereby proving
the near-optimality of its spanning ratio and the near-optimality of the routing ratio
of both our routing algorithms.
| Identifer | oai:union.ndltd.org:uottawa.ca/oai:ruor.uottawa.ca:10393/36574 |
| Date | January 2017 |
| Creators | Paradis, Frédérik |
| Contributors | Dujmovic, Vida, De Carufel, Jean-Lou, Bose, Prosenjit |
| Publisher | Université d'Ottawa / University of Ottawa |
| Source Sets | Université d’Ottawa |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.002 seconds