Local Routing in Spanners Based on WSPDs

Abstract

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.