Compute Canada

View All Papers
To Submit a new publication, Please visit the User's Section (logged in users only)

Publications:

To view a publication's Abstract (if available), click on publication's title

Author(s)

     Paz Carmi, Mathieu Couture, Michiel Smid, Daming Xu, Prosenjit Bose

Title

     On a family of strong geometric spanners that admit local routing strategies

Publication Name

     10th International Workshop on Algorithms and Data Structures (WADS)

Publication Type

     
Publisher
     Springer
Place
      Halifax, Canada
Editor(s)
     
Number
     
School
      Scool of Computer Science, Carleton University
Volume
     
Chapter
     
Pages
     
Other Publication Information
     
Publication Year
     2007
Abstract
     We introduce a family of directed geometric graphs, denoted G(lambda,theta), that depend on two parameters lambda and theta. For 0 <= theta < pi/2 and 1/2 < lambda < 1, the G(lambda,theta) graph is a strong t-spanner, with t=1/((1-lambda)cos(theta)). The out-degree of a node in the G(lambda,theta) graph is at most floor(2pi/(min(theta, arccos(1/2lambda))). Moreover, we show that routing can be achieved locally on G(lambda,theta). Next, we show that all strong t-spanners are also t-spanners of the unit disk graph. Simulations for various values of the parameters lambda and theta indicate that for random point sets, the spanning ratio of G(lambda,theta) is better than the proven theoretical bounds.
Keywords
     
Website
     http://cg.scs.carleton.ca/~mathieu/publications.html
Paper Status
     Accepted
DOI / Publication ID
     



View All Papers