Synopses & Reviews
Synopsis
Excerpt from On Shortest Paths Between Two Convex Polyhedra
We consider the problem of computing the shortest path between two points in three-dimensional space bounded by a collection of convex and disjoint polyhedral obstacles. Although this problem is hard to solve for arbitrarily many obstacles, it had been efficiently solved by Mount Mo84] (cf. also Sharir and Schorr SS84]) for a single convex polyhedral obstacle, in time O(nlog n), where n is the number of faces of the obstacle. In this paper we generalize this technique to the case of two convex polyhedral obstacles, and present an algorithm which solves this problem in time O(n3a(n)⁰(ᵃ(ⁿ)log n), where a(n) is the functional inverse of Ackermann's function, and is thus extremely slowly growing. This result is achieved by constructing a new kind of Voronoi diagram, called peeper's Voronoi diagram, which we introduce and analyze in this paper.
1. Introduction
Shortest path planning in Euclidean space bounded by obstacles is a problem arising in robotics, and is a special case of the problem of planning optimal collision free paths of a given robot system moving amidst a collection of known obstacles, between an initial position and a desired final position. In general this problem is quite hard, and the notion of optimality is not easy to define, but if the robot system is taken to be a single moving point, and the obstacles are assumed to be a collection of polyhedral bodies, we obtain the somewhat easier Euclidean shortest path problem.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.
Synopsis
Excerpt from On Shortest Paths Between Two Convex Polyhedra
As a matter of fact, the problem we face here can be formulated as that of calculating all possible sequences of edges of B which can be crossed by shortest paths from any point on e to any point on e'. If we had all these sequences available, then we could unfold each such sequence C in turn so as to make the middle portion of the corresponding candidate path into a straight segment, and then find the shortest path from so to Z constrained to contain such a segment, a task which can be accomplished in much the same way as was done in Sections 3 and 4.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.