Optimizing a constrained convex polygonal annulus

In this paper we give solutions to several constrained polygon annulus placement problems for offset and scaled polygons, providing new efficient primitive operations for computational metrology and dimensional tolerancing. Given a convex polygon P and a planar point set S, the goal is to find the thinnest annulus region of P containing S. Depending on the application, there are several ways this problem can be constrained. In the variants that we address the size of the polygon defining the inner (respectively, outer) boundary of the annulus is fixed, and the annulus is minimized by minimizing (respectively, maximizing) the outer (respectively, inner) boundary. We also provide solutions to a related known problem: finding the smallest homothetic copy of a polygon containing a set of points. For all of these problems, we solve for the cases where smallest and largest are defined by either the offsetting or scaling of a polygon. We also provide some experimental results from implementations of several competing approaches to a primitive operation important to all the above variants: finding the intersection of n copies of a convex polygon.