The Algebraic Complexity of Shortest Paths in Polyhedral Spaces
Chanderjit Bajaj · Purdue e-Pubs (Purdue University System) · 1985
In this paper we show that the problem of finding the shortest path between two points in Euclidean 3-space, bounded by a finite collection of polyhedral obstacles, is in general not solvable by radicals over the field of rationals.The problem is shown to be not solvable even for the case when only two obstacle edges are encountered in the shof[est path in 3-space.One direct consequence of the non-solvability by radicals is that for the shortest path problem there cannot exist an exac:t algorhhm under models of computation where the root of an algebraic equation is obtained using arithmetic operations and the extraction of err roots.This leaves only numerical or :;ymbolic approximations to the solutions, where the complexity of the approximations is primarily a function of the algebraic degree of the optimum solu~ tion.For special relative orientations of the polyhedral obstacles however the shortest path is ShOWll to be straight-edge and compass constructible.Simple polynomial time exact algorithms are known for such cases.