Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Papadimitriou's approximation approach to the Euclidean shortest path (ESP) problem in 3-space is revisited. As this problem is NP-hard, his approach represents an important step towards practical algorithms. Unfortunately, there are non-trivial gaps in the original description. Besides giving a complete treatment, we also give an alternative to his subdivision method which has some nice properties. Among the tools needed are root-separation bounds and non-trivial applications of Brent's complexity bounds on evaluation of elementary functions using floating point numbers.

REFERENCES

• 1: Richard P. Brent, Fast Multiple-Precision Evaluation of Elementary Functions, Journal of the ACM (JACM), v.23 n.2, p.242-251, April 1976 [doi>10.1145/321941.321944]
• 2: J. Canny and J. H. Reif. New lower bound techniques for robot motion planning problems. IEEE Foundations of Computer $czence, 28:49-60, 1987.
• 3: K. Clarkson, Approximation algorithms for shortest path motion planning, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.56-65, January 1987, New York, New York, United States [doi>10.1145/28395.28402]
• 4: Herbert Edelsbrunner , Leonidas Guibas , János Pach , Richard Pollack , Raimund Seidel , Micha Sharir, Arrangements of curves in the plane—topology, combinatorics, and algorithms, Theoretical Computer Science, v.92 n.2, p.319-336, 20 Jan. 1992 [doi>10.1016/0304-3975(92)90319-B]
• 5: H. Lass. Vector and Tensor Analysis. McGraw- Hill, 1950.
• 6: C. H. Papadimitriou. An algorithm for shortestpath motion in three dimensions. Inform. Process. Lett., 20:259-263, 1985.
• 7: Subhash Suri and John Hershberger. Efficient computation of euclidean shortest paths in the plane. IEEE Foundations of Computer Science, pages 508-517, 1993. An improved O(nlogn) bound was recently announced.
• 8: Chee Yap. Towards exact geometric computation. In Fifth Canadian Conference on Computational Geometry, pages 405-419, Waterloo, Canada, August 5-9 1993. Invited Lecture.
• 9: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory