Minimum Enclosures with Specified Angles

Loading...
Thumbnail Image

Files

CS-TR-3219.ps (154.7 KB)
No. of downloads: 263
CS-TR-3219.pdf (156.22 KB)
No. of downloads: 845

Publication or External Link

Date

1998-10-15

Advisor

Citation

DRUM DOI

Abstract

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 = ((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)

Notes

Rights