Abstract:
This paper considers the calculation of a Euclidean shortest
path (ESP) in a three-dimenisonal (3D) polyhedral space II. We propose
an approximate K(E).O(M|V|)
3D ESP algorithm (excluding preprocessing), with preprocessing time
complexity O(M|E| + |S| + |V| log |V|) for solving a special, but `fairly
general' case of the 3D ESP problem, where does not need to be
convex, V and E are the sets of vertices and edges of , respectively,
and S is the set of faces (triangles) of II; M is the maximal number of
vertices of a so-called critical polygon; K(E)=(Lo-L)/E
where Lo is the length of the initial path and L is the true (i.e., optimum)
path length. The given algorithm solves approximately three (previously
known to be) NP-complete or NP-hard 3D ESP problems in time K(E).O(k) where k is the number of layers in a stack, which is introduced
in this paper as the problem environment. The proposed approximation
method is only an example of a general technique, for which the authors
also see further potentials to support e cient approximate solutions for
more general 3D ESP problems.
Description:
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the original MI_tech website http://www.mi.auckland.ac.nz/index.php?option=com_content&view=article&id=91&Itemid=76 . All other rights are reserved by the author(s).