SINGLE-EXPONENTIAL UPPER BOUND FOR FINDING SHORTEST PATHS IN 3 DIMENSIONS

被引：16

作者：

REIF, JH ^{[1
]}

STORER, JA ^{[1
]}

机构：

[1] BRANDEIS UNIV, CTR COMPLEX SYST, DEPT COMP SCI, WALTHAM, MA 02254 USA

来源：

JOURNAL OF THE ACM | 1994年 / 41卷 / 05期

关键词：

ALGORITHMS; PERFORMANCE; MINIMAL MOVEMENT PROBLEM; MOTION PLANNING; MOVERS PROBLEM; ROBOTICS; SHORTEST PATH; THEORY OF REAL CLOSED FIELDS; 3-DIMENSIONAL EUCLIDEAN SPACE;

D O I：

10.1145/185675.185811

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected.

引用

页码：1013 / 1019

页数：7

共 22 条

[1] Aho A. V., 1974, DESIGN ANAL COMPUTER
[2] PARTITIONING A POLYGONAL REGION INTO TRAPEZOIDS
ASANO, T
ASANO, T
IMAI, H
[J]. JOURNAL OF THE ACM, 1986, 33 (02) : 290 - 312
[3] BAJAJ C, 1986, P IEEE INT C ROBOTIC
[4] BAJAJ C, 1985, 23RD P ALL C
[5] ON THE SHORTEST PATHS BETWEEN 2 CONVEX POLYHEDRA
BALTSAN, A
SHARIR, M
[J]. JOURNAL OF THE ACM, 1988, 35 (02) : 267 - 287
[6] BENOR M, 1984, 16TH P ANN ACM S THE, P457
[7] Canny J., 1987, 28th Annual Symposium on Foundations of Computer Science (Cat. No.87CH2471-1), P49, DOI 10.1109/SFCS.1987.42
[8] CHISTOV AL, 1985, COMPLEXITY QUANTIFIE
[9] CLARKSON K, 1987, 19TH P ANN ACM S THE, P56
[10] Collins G. E., 1975, LECT NOTES COMPUT SC, V33, P134, DOI [DOI 10.1007/3-540-07407-4_17, 10.1007/3-540-07407-4_17]

← 1 2 3 →