Euclidean Shortest Paths

Exact or Approximate Algorithms

By Fajie Li , Reinhard Klette

Euclidean Shortest Paths Cover Image

This book reviews algorithms for the exact or approximate solution of shortest-path problems, with a specific focus on a class of algorithms called rubberband algorithms. The coverage includes mathematical proofs for many of the given statements.

Full Description

  • ISBN13: 978-1-4471-2255-5
  • 393 Pages
  • User Level: Science
  • Publication Date: November 3, 2011
  • Available eBook Formats: PDF
  • eBook Price: $129.00
Buy eBook Buy Print Book Add to Wishlist

Related Titles

Full Description
This unique text/reference reviews algorithms for the exact or approximate solution of shortest-path problems, with a specific focus on a class of algorithms called rubberband algorithms. Discussing each concept and algorithm in depth, the book includes mathematical proofs for many of the given statements. Topics and features: provides theoretical and programming exercises at the end of each chapter; presents a thorough introduction to shortest paths in Euclidean geometry, and the class of algorithms called rubberband algorithms; discusses algorithms for calculating exact or approximate ESPs in the plane; examines the shortest paths on 3D surfaces, in simple polyhedrons and in cube-curves; describes the application of rubberband algorithms for solving art gallery problems, including the safari, zookeeper, watchman, and touring polygons route problems; includes lists of symbols and abbreviations, in addition to other appendices.
Table of Contents

Table of Contents

  1. Part I: Discrete or Continuous Shortest Paths.
  2. Euclidean Shortest Paths.
  3. Deltas and Epsilons.
  4. Rubberband Algorithms.
  5. Part II: Paths in the Plane.
  6. Convex Hulls in the Plane.
  7. Partitioning a Polygon or the Plane.
  8. Approximate ESP Algorithms.
  9. Part III: Paths in Three
  10. Dimensional Space.
  11. Paths on Surfaces.
  12. Paths in Simple Polyhedrons.
  13. Paths in Cube Curves.
  14. Part IV: Art Galleries.
  15. Touring Polygons.
  16. Watchman Route.
  17. Safari and Zookeeper Problems.
Errata

Please Login to submit errata.

No errata are currently published