Minimum-perimeter enclosures

We give the first polynomial-time algorithm for the problem of finding a minimum-perimeter k-gon that encloses a given n-gon. Our algorithm is based on a simple structural result, that an optimal k-gon has at least one “flush” edge with the n-gon. This allows one to reduce the problem to computing a shortest k-link path in a simple polygon. As a by-product we observe that the minimum-perimeter “envelope”—a convex polygon with a specified sequence of interior angles—can also be found in polynomial time. Finally, we introduce the problem of finding optimal convex polygons restricted to lie in the region between two nested convex polygons. We give polynomial-time algorithms for the problems of finding the minimum restricted envelopes.