An improved algorithm for the automated design of large-scaled robot skin

A recent paper titled 'On the Problem of the Automated Design of Large-Scaled Robot Skin' (Anghinolfi et al., 2013) published in the IEEE Transactions on Automation Science and Engineering addressed the problem of covering the surface of a humanoid robot with the largest number of nonoverlapping equilateral triangular sensor modules. The problem is eventually approximated by a simpler one: how to find the placement of a given polygon P on an equilateral triangular grid G that contains the largest number of the grid triangles. In this paper, we show how to improve the efficiency of the algorithm presented in that paper. Further, we show that the general problem of filling P with the largest number of disjoint equilateral triangles (all entirely contained in P and all of the same size) is not equivalent to that of finding an optimal placement of P on G. Using this result, we propose an improved heuristic for the original problem of covering the skin of a robot with the largest number of triangular sensor modules. Note to Practitioners - The problem of fitting the largest number of nonoverlapping triangles of an isometric triangular grid in the interior of a simple polygon is very useful, e.g., for computing how to cover the skin of a robot with triangular electronic sensors. We show that the information of the number of triangles that are contained in the interior of a polygon in a given placement can be obtained efficiently by our proposed algorithm. This is a significant improvement over the algorithm provided in Anghinolfi et al., 2013. Furthermore, each connected set of contained triangles can be reported in time linear to the size of the set. Our proposed algorithm is simple and practical, and it can be adapted to efficiently compute the number of cells that are contained in a grid with a tiling of regular polygons.