This paper introduces the concept of precision-sensitive algorithms, analogous to the well-known output-sensitive algorithms. We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem. Specifically, we analyze an incremental approximation approach and show that this approach yields an asymptotic improvement of running time. By using an optimization technique to improve paths on fixed edge sequences, we modify this algorithm to guarantee a relative error of O(2 -r ) in a time polynomial in r and $1/\delta$, where $\delta$ denotes the relative difference in path length between the shortest and the second shortest path. Our result is the best possible in some sense: if we have a strongly precision-sensitive algorithm, then we can show that unambiguous SAT (USAT) is in polynomial time, which is widely conjectured to be unlikely. Finally, we discuss the practicability of this approach. Experimental results are provided.

No abstract available.

Motion planning involving arbitrarily many degrees of freedom is known to be PSPACE-hard. In this paper, we examine the complexity of generalized motion-planning problems for planar mechanisms consisting of independently movable objects. Our constructions constitute a general framework for reducing problems in information processing to motion planning, leading to easy proofs of known PSPACE-hardness results and to exponential lower bounds for geometrical problems related to motion planning. Particulalrly, we show that the problem of deciding whether a given mechanism A can always avoid a collision with another mechanism B is EXPSPACE-hard. New lower bounds are also obtained for the problem of planning under given physical side conditions. We consider the case that certain motions require forces, e.g., to subdue friction, and ask for motions that stay under a given energy limit. Within our framework, we show that such shortest-path problems are EXPTIME-hard if we use number representations by mantissa and exponent, and even undecidable if we allow that some motions require no force or an infinite amount. The proof consists of a simulation of Turing machines with infinite tape and shows that the notion of Turing computability can be interpreted in purely geometrical terms. The geometrical model obtained is capable of expressing a variety of physical-planning problems.

This paper introduces the concept of precisionsensitive algorithms, in analogy to the well-known output-sensitive algorithms.We exploit this idea in studying the complexity of the 3-dimensional Euclidean shortest path problem.

We examine shortest path planning under a direction weighted Euclidean metric, motivated by the problem of finding optimal routes for sailboats. We show that for piecewise linear weight functions the shortest path in the unrestricted plane always consists of 2 line segments, and by this solve the problem in a polygonal environment with a visibility graph approach. We then investigate the problem in a general setting, in which the weighted distance measure is supplemented by a link distance measure, and present polynomial approximation algorithms for this case.

We consider the problem of planning curvature constrained paths amidst polygonal obstacles, connecting the given start and target configurations. Let the critical curvature R/sub c//sup -1/ be the minimal curvature for which a constrained path exists. We describe an algorithm which approximates the critical curvature and finds a corresponding path. Further, we give an efficient decision procedure to determine if there exists a path satisfying the given curvature constraint R/sup -1/, with running time polynomial in |R-R/sub c/|/R.

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.