Minimum enclosures with specified angles
David M. Mount, Ruth Silverman · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1993
Given a convex polygon P, an m-envelope is a convex m-sided polygon that contains P. Given any convex polygon P, and any sequence of m >= 3 angles A equals ((alpha) 1, (alpha) 2, ..., (alpha) m) we consider the problem of computing the minimum area m- envelope for P whose counterclockwise sequence of exterior angles is given by A. We show that such envelopes can be computed in O(nm log m) time. The main result on which the correctness of the algorithm rests is a flushness condition stating that for any locally minimum enclosure with specified angles, one of its sides must be collinear with one of the sides of P.