The Problem of Shortest Path in 3D Space
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    Abstract:

    The problem of computing the euclidean shortest path between two points in the three dimensional space bounded by a collection of convex disjoint polyhedral obstacles is known to be NP-hard and in exponential time for arbitrarily many obstacles. It can be solved in O(n2) time for single convex polyhedron obstacle (here n is the total number of vertices of polyhedron). In this paper, the author mainly researchs the shortest problem of the case of two convex polyhedral obstacles, and presents an algorithm that solves this problem in O(n2) time, and improves improving significantly previous best result On3logn) for this special case. On the other hand, the author also presents a better result O(∑12i-1n2i) for the problem of shortest path amidst a fixed number of convex polyhedral obstacles.

    Reference
    Related
    Cited by
Get Citation

施海虎.三维空间中的最短路问题.软件学报,1999,10(7):772-777

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:November 11,1997
  • Revised:July 20,1998
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063