Shortest path amidst disc obstacles is computable

ABSTRACT

An open question in Exact Geometric Computation is whether there re transcendental computations that can be made "geometrically exact".Perhaps the simplest such problem in computational geometry is that of computing the shortest obstacle-avoiding path between two points p, q in the plane, where the obstacles re collection of n discs.This problem can be solved in O (n 2 log n)time in the Real RAM model, but nothing was known about its computability in the standard (Turing) model of computation. We first show the Turing-computability of this problem,provided the radii of the discs are rationally related. We make the usual assumption that the numerical input data are real algebraic numbers. By appealing to effective bounds from transcendental number theory, we further show single-exponential time upper bound when the input numbers are rational.Our result ppears to be the first example of non-algebraic combinatorial problem which is shown computable. It is also rare example of transcendental number theory yielding positive computational results.

REFERENCES

• 1: A. Baker. Transcendental Number Theory. Cambridge University Press, 1979.
• 2: Lenore Blum , Felipe Cucker , Michael Shub , Steve Smale, Complexity and real computation, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 3: C. Burnikel , R. Fleischer , K. Mehlhorn , S. Schirra, Efficient exact geometric computation made easy, Proceedings of the fifteenth annual symposium on Computational geometry, p.341-350, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304988]
• 4: J. H. Conway, C. Radin, and L. Sadun. On angles whose squared trigonometric functions are rational. Discrete and Computational Geometry, 22:321--332, 1999.
• 5: Z. Du, M. Eleftheriou, J. Moreira, and C. Yap. Hypergeometric functions in exact geometric computation. In V.Brattka, M.Schoeder, and K.Weihrauch, editors, Proc. 5th Workshop on Computability and Complexity in Analysis, pages 55--66, 2002. Malaga, Spain, July 12-13, 2002. In Electronic Notes in Theoretical Computer Science, 66:1 (2002), www.elsevier.nl/locate/entcs/volume66.html.
• 6: Z. Du and C. Yap. Absolute approximation of the general hypergeometric function, Mar. 2005. Preprint: abs-approx.ps.gz from ftp://cs.nyu.edu/pub/local/yap/exact/.
• 7: A. Fabri, E. Fogel, B. Gärtner, M. Hoffmann, L. Kettner, S. Pion, M. Teillaud, R. Veltkamp, and M. Yvinec. The CGAL manual. 2003. Release 3.0.
• 8: N. Fel'dman and Y. V. Nesterenko. Number Theory IV: Transcendental Numbers, volume 44 of Encycolpaedia of Mathematical Sciences. Springer-Verlag, Berlin, 1998. Translated from Russian by N. Koblitz.
• 9: J. Jahnel. When does the (co)sine of a rational angle give a rational number?, 2004. From www.uni-math.gwdg.de/jahnel/linkstopaperse.html.
• 10: V. Karamcheti , C. Li , I. Pechtchanski , C. Yap, A core library for robust numeric and geometric computation, Proceedings of the fifteenth annual symposium on Computational geometry, p.351-359, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304989]
• 11: David Kincaid , Ward Cheney, Numerical analysis: mathematics of scientific computing (2nd ed), Brooks/Cole Publishing Co., Pacific Grove, CA, 1996
• 12: S. Lang. Introduction to Transcendental Numbers. Addison-Wesley, Reading, Massachusetts, 1996.
• 13: K. Mehlhorn and S. Schirra. Exact computation with ledareal -- theory and geometric application. In G. Alefeld, J. Rohn, S. Rump, and T. Yamamoto, editors, Symbolic Algebraic Methods and Verification Methods, volume 379, pages 163--172, Vienna, 2001. Springer-Verlag.
• 14: Daniel Richardson, How to recognize zero, Journal of Symbolic Computation, v.24 n.6, p.627-645, Dec. 1997 [doi>10.1006/jsco.1997.0157]
• 15: D. Richardson and A. El-Sonbaty. Counterexamples to the uniformity conjecture. Comput. Geometry: Theory and Appl., 2004. Special Issue on Robust Geometric Algorithms and its Implementations, Eds. C. Yap and S. Pion. To appear.
• 16: M. Waldschmidt. Transcendence measures for exponentials and logarithms. J. Austral. Math. Soc. Ser. A, 25(4):445--465, 1978.
• 17: M. Waldschmidt. A lower bound for linear forms in logarithms. Acta Arith., 37:257--283, 1980.
• 18: Klaus Weihrauch, Computable analysis: an introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 2000
• 19: Chee Keng Yap, Fundamental problems of algorithmic algebra, Oxford University Press, Inc., New York, NY, 1999
• 20: C. K. Yap. On guaranteed accuracy computation. In F. Chen and D. Wang, editors, Geometric Computation, chapter 12, pages 322--373. World Scientific Publishing Co., Singapore, 2004.
• 21: Chee K. Yap, Robust geometric computation, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
disc obstacles, exact geometric computation, exponential complexity, guaranteed precision computation, real RAM model, robust numerical algorithms, shortest path