Skip to content
Register Sign in Wishlist
Geometric Spanner Networks

Geometric Spanner Networks

CAD$206.95 (C)

  • Date Published: January 2007
  • availability: Available
  • format: Hardback
  • isbn: 9780521815130

CAD$ 206.95 (C)

Add to cart Add to wishlist

Other available formats:

Looking for an examination copy?

This title is not currently available for examination. However, if you are interested in the title for your course we can consider offering an examination copy. To register your interest please contact providing details of the course you are teaching.

Product filter button
About the Authors
  • Aimed at an audience of researchers and graduate students in computational geometry and algorithm design, this book uses the Geometric Spanner Network Problem to showcase a number of useful algorithmic techniques, data structure strategies, and geometric analysis techniques with many applications, practical and theoretical. The authors present rigorous descriptions of the main algorithms and their analyses for different variations of the Geometric Spanner Network Problem. Though the basic ideas behind most of these algorithms are intuitive, very few are easy to describe and analyze. For most of the algorithms, nontrivial data structures need to be designed, and nontrivial techniques need to be developed in order for analysis to take place. Still, there are several basic principles and results that are used throughout the book. One of the most important is the powerful well-separated pair decomposition. This decomposition is used as a starting point for several of the spanner constructions.

    • The first monograph on geometric spanners
    • Great attention to details; algorithms and proofs are presented in as much detail as possible
    • Some of the analysis has not appeared in such detail in literature
    Read more

    Reviews & endorsements

    "The writing style is clear, with a clean presentation enriched with boxes highlighting important contents and figures."
    David Orden, Mathematical Reviews

    Customer reviews

    Not yet reviewed

    Be the first to review

    Review was not posted due to profanity


    , create a review

    (If you're not , sign out)

    Please enter the right captcha value
    Please enter a star rating.
    Your review must be a minimum of 12 words.

    How do you rate this item?


    Product details

    • Date Published: January 2007
    • format: Hardback
    • isbn: 9780521815130
    • length: 516 pages
    • dimensions: 260 x 185 x 34 mm
    • weight: 1.06kg
    • availability: Available
  • Table of Contents

    Part I. Introduction:
    1. Introduction
    2. Algorithms and graphs
    3. The algebraic computation-tree model
    Part II. Spanners Based on Simplical Cones:
    4. Spanners based on the Q-graph
    5. Cones in higher dimensional space and Q-graphs
    6. Geometric analysis: the gap property
    7. The gap-greedy algorithm
    8. Enumerating distances using spanners of bounded degree
    Part III. The Well Separated Pair Decomposition and its Applications:
    9. The well-separated pair decomposition
    10. Applications of well-separated pairs
    11. The Dumbbell theorem
    12. Shortcutting trees and spanners with low spanner diameter
    13. Approximating the stretch factor of Euclidean graphs
    Part IV. The Path Greedy Algorithm:
    14. Geometric analysis: the leapfrog property
    15. The path-greedy algorithm
    Part V. Further Results and Applications:
    16. The distance range hierarchy
    17. Approximating shortest paths in spanners
    18. Fault-tolerant spanners
    19. Designing approximation algorithms with spanners
    20. Further results and open problems.

  • Authors

    Giri Narasimhan, Florida International University
    Giri Narasimhan earned a B.Tech. in Electrical Engineering from the Indian Institute of Technology in Mumbai, India, and a Ph.D. in Computer Science from the University of Wisconsin in Madison, Wisconsin, USA. He was a member of the faculty at the University of Memphis, and is currently at Florida International University.

    Michiel Smid, Carleton University, Ottawa
    Michiel Smid received a M.Sc. degree in Mathematics from the University of Technology in Eidenhoven and a Ph.D. degree in Computer Science from the University of Amsterdam. He has held teaching positions at the Max-Planck-Institute for Computer Science in Saarbrucken, King's College in London, and the University of Magdenburg. Since 2001, he has been at Carleton University, where he is currently a professor of Computer Science.

Sign In

Please sign in to access your account


Not already registered? Create an account now. ×

Sorry, this resource is locked

Please register or sign in to request access. If you are having problems accessing these resources please email

Register Sign in
Please note that this file is password protected. You will be asked to input your password on the next screen.

» Proceed

You are now leaving the Cambridge University Press website. Your eBook purchase and download will be completed by our partner Please see the permission section of the catalogue page for details of the print & copy limits on our eBooks.

Continue ×

Continue ×

Continue ×

Find content that relates to you

Join us online

This site uses cookies to improve your experience. Read more Close

Are you sure you want to delete your account?

This cannot be undone.


Thank you for your feedback which will help us improve our service.

If you requested a response, we will make sure to get back to you shortly.

Please fill in the required fields in your feedback submission.