文章基本信息

标题：An Efficient Algorithm for Touring n Circles
本地全文：下载
作者：Yuepeng Ding ; Xiong Xie ; Bo Jiang 等
期刊名称：MATEC Web of Conferences
电子版ISSN：2261-236X
出版年度：2018
卷号：232
DOI：10.1051/matecconf/201823203027
语种：English
出版社：EDP Sciences
摘要：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≤nunder 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.