Placing registration marks

The registration mark problem is defined, as follows. Given an n-sided rigid planar polygonal part and a set of k planar geometric transforms, locate a point on the surface of the part that maximizes the minimum distance between transformed points. A registration mark at this point will be maximally robust to sensor imperfections. An O(n log²k+k ⁴ log k log*k) time algorithm for solving this planar problem is given, and the result is demonstrated using the Image-Calc vision system. The results extend to curved planar parts and polyhedral parts. How part shape can be redesigned to simplify localization is considered. In essence, it is shown how to design the surface of a part to facilitate automated assembly