Covering points with a polygon

We consider problems in which we try to cover a given set of points (or a maximum number of them) with a given polygon. To solve these problems we use a new type of diagram that captures point-containment information for scalable, rotated, and/or translated versions of convex polygons. For a given polygon P and a contact point q in a point set S, the diagram parameterizes possible translations, rotations, and scales of P in order to represent containment regions for every other point v∈S. We present geometric and combinatorial properties of this diagram, and describe how it can be computed and used in the solution of several geometric matching problems. The latter have direct applications to object recognition and tolerancing problems in manufacturing.