The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Precision-Sensitive Euclidean Shortest Path in 3-Space
Jurgen Sellen, Joonsoo Choi, Chee-Keng Yap,
Pages. 1577-1595
Abstract 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.
Contents 1. Introduction 2. Preliminaries 3. Combinatorial 3ESP is as hard as USAT 4. Approximation 5. Experimental results 6. Final remarks
Key words shortest path, exact geometric algorithms, bit complexity, precision-sensitivity
Mathmatical Subject Classification 68Q25, 68U05