An Efficient Algorithm for Touring n Circles

Dalian Maritime University , Linghai Road 1, Dalian, China

^* Corresponding author: aBo Jiang: bojiang@dlmu.edu.cn

Abstract

This paper proposed an intelligent algorithm, which can build the shortest path of the intersecting circle sequences in the plane. The problem is transformed to a corresponding problem of computing the shortest path of three disjoint circles. And it is also an in-depth study of the traversal problem for the disjoint circle sequences. On the basis of the previous work, the algorithms are developed to construct such shortest path in polynomial time of O(kn) where 1≤k≤n under a given computational threshold. Since the algorithm is fully polynomial time consuming, this work can be conducted in layered manufacturing of rapid prototyping, displacement of wireless sensor networks, or other related computer-aided design and manufacturing applications.