Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/41131
Title: Shortest path AMIDST disc obstacles is computable
Authors: Chang, E.-C. 
Choi, S.W.
Kwon, D.Y.
Park, H.
Yap, C.K.
Keywords: Computability
Disc obstacles
Exact geometric computation
Exponential complexity
Guaranteed precision computation
Real RAM model
Robust numerical algorithms
Shortest path
Transcendental number theory
Issue Date: 2006
Source: Chang, E.-C.,Choi, S.W.,Kwon, D.Y.,Park, H.,Yap, C.K. (2006). Shortest path AMIDST disc obstacles is computable. International Journal of Computational Geometry and Applications 16 (5-6) : 567-590. ScholarBank@NUS Repository.
Abstract: An open question in Exact Geometric Computation is whether there are 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 are a 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 give a direct proof of 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 a single-exponential time upper bound when the input numbers are rational. Our result appears to be the first example of a non-algebraic combinatorial problem which is shown computable. It is also a rare example of transcendental number theory yielding positive computational results. © World Scientific Publishing Company.
Source Title: International Journal of Computational Geometry and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/41131
ISSN: 02181959
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

52
checked on Dec 9, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.