Polygon approximation with optimized polygonal enclosures: applications and algorithms
N. Adlai A. De Pano · 1987
Computational Geometry is a new branch of research in the larger field of algorithm design and analysis. In his ground-breaking thesis (Sh78), M. I. Shamos writes in his abstract: (Computational Geometry) is a study of the computational aspects of geometry within the framework of analysis of algorithms. In this current thesis, we continue this trend of recasting classical geometric notions in the light of present-day computational capabilities. It is often useful and sometimes crucial to be able to represent complex geometric objects using simpler substitutes that somehow capture the original objects' properties. For example, in two-dimensional space, one could use polygonal enclosures to model the clutter that might lie in a robot's locus of operation. Or, the enclosures may represent packaging schemes for products with complex shapes. We look at different criteria by which such enclosures may be optimized. Among these are area, perimeter, number of edges or vertices, and clearance. The analysis is limited to the two-dimensional case, although a number of results do find extensions in higher dimensions. The typical problem that is analyzed in this work can be stated as follows: Given a polygon on the plane with property A, find an approximating polygon with property B that optimizes criterion C. A rich collection of problems is analyzed and solutions are characterized. Algorithms are then designed based on these characterizations and their complexity estimated. The main contributions presented are optimal procedures for computing minimum-area (minimum-perimeter) equiangular enclosures, a characterization that makes possible the best-known solution for the unrestricted minimum-area k-gonal enclosure problem, characterization and solution of the unrestricted minimum-perimeter triangular enclosure problem, and characterization of various other modes of polygon approximation. A number of remaining open problems are discussed at the conclusion of the work.