Minimum Enclosures with Specified Angles
| dc.contributor.author | Mount, David M. | en_US |
| dc.contributor.author | Silverman, Ruth | en_US |
| dc.date.accessioned | 2004-05-31T21:01:57Z | |
| dc.date.available | 2004-05-31T21:01:57Z | |
| dc.date.created | 1994-02 | en_US |
| dc.date.issued | 1998-10-15 | en_US |
| dc.description.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) | en_US |
| dc.format.extent | 158413 bytes | |
| dc.format.mimetype | application/postscript | |
| dc.identifier.uri | http://hdl.handle.net/1903/405 | |
| dc.language.iso | en_US | |
| dc.relation.isAvailableAt | Digital Repository at the University of Maryland | en_US |
| dc.relation.isAvailableAt | University of Maryland (College Park, Md.) | en_US |
| dc.relation.isAvailableAt | Tech Reports in Computer Science and Engineering | en_US |
| dc.relation.isAvailableAt | Computer Science Department Technical Reports | en_US |
| dc.relation.ispartofseries | UM Computer Science Department; CS-TR-3219 | en_US |
| dc.relation.ispartofseries | CAR-TR-701 | en_US |
| dc.title | Minimum Enclosures with Specified Angles | en_US |
| dc.type | Technical Report | en_US |