A Base Algorithm for Computing the Shortest Path of Spheres
Computing the shortest path among a plural number of spherical balls is essential in 3D computer graphics. The problem of finding the shortest path of three spheres is fundamental to the more general n-sphere problem. Two major contributions of this paper are: proposing an exact algorithm to rapidly computing the shortest path of three spheres in 3D as the base algorithm for the general n-sphere problem, and discussing several intriguing findings in its degenerated 2D model which consolidates the correctness of this work. First of all, the problem is reduced to a corresponding problem of computing the shortest path of three coplanar circles, and turns out to a two points and one circle path planning problem.