Reshaping Convex Polyhedra PDF Download

Excerpt from On Shortest Paths Amidst Convex Polyhedra Let K be a 3-D convex polyhedron having n vertices. A sequence of edges of K is called a shortest-path sequence if there exist two points X, Y on the surface S of K such that is the sequence of edges crossed by the shortest path from X to Y along S. We show that the number of shortest-path sequences for K is polynomial inn, and as a consequence prove that the shortest path between two points in 3-space which must avoid the interiors of a fixed number of disjoint convex polyhedral obstacles, can be calculated in time polynomial in the total number of vertices of these obstacles (but exponential in the number of obstacles). 1. Introduction In this paper we study several problems related to the problem of calculating the Euclidean shortest path between two points in 3-dimensional space, which must avoid the interiors of a collection of polyhedral obstacles having altogether n vertices. This general problem seems to be intractable, and the only known algorithms for it require exponential time ([SS], [RS]), although no lower bounds are known as yet for this problem. On the other extreme hand we have the problem of finding the shortest path between two points in 3-space which must avoid the interior of a single convex polyhedral obstacle. In this case the problem is solvable in time 0(n log n) ([SS], [Mo]). Interpolating between these two extreme cases, one might consider the problem in which the polyhedral obstacles consist of a fixed number k of disjoint convex polyhedra (having altogether n vertices), and attempt to calibrate the complexity of this problem as a function of k and n. 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."