The Optimal Approach to the Painting Problems on Polygonal Surfaces

摘要

We proposed a novel method to the painting problems according to the concepts of triangulation meshes and spanning-tree based approach to find the complete area coverage path with minimum length and O(nlogn) time complexity, where n denotes the number of triangles. In our algorithm, a mobile robot is guided through a sequence of areas to be covered without consuming energy and time, and the robot will return to the starting point at the end. Based on our knowledge, this is the fastest method with minimum length addressing the complete area coverage problem for painter robots on polygonal surfaces.