Minimum Enclosures with Specified Angles

TitleMinimum Enclosures with Specified Angles
Publication TypeReports
Year of Publication1998
AuthorsMount D, Silverman R
Date Published1998/10/15/
InstitutionDepartment of Computer Science, University of Maryland, College Park
KeywordsTechnical Report

Given a convex polygon P, an m-envelope is a convex m-sidedpolygon that contains P. Given any convex polygon P, and any sequence of m
> 3 angles A = ((11Xct2X@..ckm) we consider the problem of computing
the minimum area m-envelope for P whose counte rclockwise 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.
(Also cross-referenced as CAR-TR-701)