Exactly solvable and unsolvable shortest network problems in 3D-space

Abstract

A problem is defined to be exactly solvable if its solution can be obtained by solving a sequence of polynomials using radicals. Therefore, if a problem is not exactly solvable, then we have to use approximation schemes for solving the problem. It has been proved that the shortest network problem in space is not exactly solvable even if the network spans only four points and even if the topology is known. On the other hand, if the network spans three points, then obviously the problem is exactly solvable. In a previous paper we have shown that the shortest network problem for three points is still exactly solvable if only one point is constrained on a straight line but it becomes non-exactly..