An algorithm for computing the shortest path of three spheres

Computing the Euclidean shortest path among a plural number of spherical balls is an interesting problem in 3D computer graphics. Finding the Euclidean shortest path of three spheres is fundamental to the more general n-sphere problem. In this paper, we develop an exact algorithm for computing the shortest path of three spheres in 3D space. The problem is firstly 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. After applying the general root formula of the shortest path of two points and one circle together with the method of axis rotation, the algorithm is build. Empirical results accompany a brute force method for comparison have shown the correctness and effectiveness of the proposed algorithm. This result can be applied in 3D computer graphics, computer-aided design and the molecular geometry.