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

共 3 条

[1] Single-exponential upper bound for finding shortest paths in three dimensions
Reif, John H., 1600, ACM, New York, NY, United States (41):
[2] Deterministic Decremental Single Source Shortest Paths: Beyond the O(mn) Bound
Bernstein, Aaron
Chechik, Shiri
STOC'16: PROCEEDINGS OF THE 48TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2016, : 389 - 397
[3] Finding Min-Sum disjoint shortest paths from a single source to all pairs of destinations
Yang, Bing
Zheng, S. Q.
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS, 2006, 3959 : 206 - 216

← 1 →