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 [J].

ASANO, T ;

IMAI, H .

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 [J].

BALTSAN, A ;

SHARIR, M .

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 →